leetcode的一道题
题意:给出一个字符串,只能在首部加上字符使其成为回文串,求所加字符数最少的方案。
这题以前搞acm的时候碰到过,如果是以前,就直接上KMP了。但是前面有道题是用manacher算法求字符串的最长回文子串。突然发现这题也可以用manacher来做,时间复杂度也是O(n)。
manacher确实是一种思路巧妙,代码简短的算法。
https://leetcode.com/problems/shortest-palindrome/
char str[1000010],ans[1000010]; int r[1000010]; int min(int a,int b){return a<b?a:b;} int max(int a,int b){return a>b?a:b;} char* shortestPalindrome(char* s) { int i,j,k,cnt; int len=strlen(s); if(len<=1) return s; r[0]=0; str[0]='?'; for(i=0;i<=len;i++) { str[(i<<1)+1]=s[i]; str[(i<<1)+2]='*'; } str[len<<1]='#';str[(len<<1)+1]='\0'; i=1;j=0; while(i<=(len<<1)) { while(str[i-j-1]==str[i+j+1]) j++; r[i]=j; for(k=1;k<=j;k++) if(r[i]-k!=r[i-k]) r[i+k]=min(r[i]-k,r[i-k]); else break; j=max(0,r[i]-k); i+=k; } for(i=(len<<1);i>=1;i--) { if(i-r[i]==1) break; } i=(i+r[i])/2; cnt=0; for(j=len-1;j>=i+1;j--) ans[cnt++]=s[j]; for(j=0;j<=len-1;j++) ans[cnt++]=s[j]; ans[cnt++]='\0'; return ans; }