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;
}