C语言 | Leetcode C语言题解之第336题回文对

题目：

题解：

#define SIZE 9470
#define N 168000
#define P 13331typedef unsigned long long ULL;
ULL p[301];//p[i]存储P^ivoid init()//初始化p进制次幂数组
{int i;p[0]=1;for(i=1;i<300;i++){p[i]=p[i-1]*P;}
}int** palindromePairs(char**words, int wordsSize, int* returnSize, int** returnColumnSizes){int **re=(int **)malloc(sizeof(int *)*N);*returnColumnSizes=(int *)malloc(sizeof(int)*N);int i,j,k;int index=0;int len;int l,r;int hash[SIZE];//存储某字符串hash值在words中的对应下标ULL key[SIZE];//存储字符串hash值，可近似认为字符串与hash值之间是一一对应的ULL t;ULL pre[301];//存储前缀字符串hash值，pre下标从1开始（即pre[i]存储某字符串前i个子字符串的哈希值），注意下标转换char *word=NULL;init();//初始化p数组memset(hash,-1,sizeof(hash));for(i=0;i<wordsSize;i++){t=0;word=words[i];for(j=strlen(word)-1;j>=0;j--)//倒序遍历计算哈希值t{t=t*P+word[j];}//第二层哈希，将hash值及对应下标存入哈希表j=t%SIZE;while(hash[j]!=-1){j=(j+1)%SIZE;}hash[j]=i;key[j]=t;}for(i=0;i<wordsSize;i++){word=words[i];len=strlen(word);pre[0]=0;for(j=0;j<len;j++)//计算前缀哈希值数组{pre[j+1]=pre[j]*P+word[j];}for(j=-1;j<len;j++)//正向查找回文串{for(l=0,r=j;l<r;l++,r--){if(word[l]!=word[r]){break;}}if(l>=r)//下标0-j是一个回文串，查找原字符串数组中是否存在j+1-末尾的翻转字符串{t=pre[len]-pre[j+1]*p[len-j-1];//j+1-末尾子字符串的哈希值k=t%SIZE;while(hash[k]!=-1&&key[k]!=t){k=(k+1)%SIZE;}if(hash[k]>=0&&hash[k]!=i)//找到了且不是自身{re[index]=(int *)malloc(sizeof(int)*2);re[index][0]=hash[k];re[index][1]=i;returnColumnSizes[0][index++]=2;if(words[hash[k]][0]==0)//空字符串，特处{re[index]=(int *)malloc(sizeof(int)*2);re[index][0]=i;re[index][1]=hash[k];returnColumnSizes[0][index++]=2;}}}}for(j=len-1;j>0;j--)//反向查找回文串{for(l=j,r=len-1;l<r;l++,r--){if(word[l]!=word[r]){break;}}if(l>=r)//下标j-末尾子字符串是回文串{t=pre[j];//前j-1个子字符串的hash值k=t%SIZE;while(hash[k]!=-1&&key[k]!=t){k=(k+1)%SIZE;}if(hash[k]>=0&&hash[k]!=i)//找到了且不是自身{re[index]=(int *)malloc(sizeof(int)*2);re[index][0]=i;re[index][1]=hash[k];returnColumnSizes[0][index++]=2;}}}}*returnSize=index;return re;
}