KMP模板

参考视频：https://www.bilibili.com/video/av3246487/

https://www.bilibili.com/video/av11866460/

https://www.bilibili.com/video/av16828557/

参考博客：https://subetter.com/algorithms-and-mathematics/kmp-algorithm.html

复杂度：$O(m+n)$

//s为母串，p为模式串
void getnext()
{
    int k=-1,j=0;
    int len=strlen(p);
    Next[0]=-1;
    while(j<len)
    {
        if(k==-1||p[k]==p[j])
        {
            k++;
            j++;
            //if(p[j]!=p[k])
            Next[j]=k;
            //else Next[j]=Next[k];
        }
        else k=Next[k];
    }
}
int KMP()
{
    getnext();
    int i=0,j=0,cnt=0;
    int slen=strlen(s);
    int plen=strlen(p);
    while(i<slen)
    {
        if(j==-1||s[i]==p[j])
        {
            i++;
            j++;
            if(j==plen)
            {
                printf("%d\n",i+1-plen);//出现的位置
                cnt++;
                j=Next[j];
            }
        }
        else j=Next[j];
    }
    return cnt;   //返回出现的次数
}

Manacher模板

参考博客：https://www.jianshu.com/p/799bc53d4e3d

复杂度：$O(n)$

char a[11000010];//aba
char anew[23000010];//$#a#b#a#
int p[23000010];//新串中以第i个字符为对称轴的回文串的回文半径
//p[i]-1为原串中以i为对称轴的最长回文串的长度

/*
* abaaba
* i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
* anew[i]: $ # a # b # a # a # b # a #
* p[i]:    1 1 2 1 4 1 2 7 2 1 4 1 2 1
* p[i]-1:  0 0 1 0 3 0 1 6 1 0 3 0 1 0
*/

void init()
{
    int len=strlen(a);
    anew[0]='$';
    anew[1]='#';
    int num=2;
    for(int i=0;i<len;i++)
    {
        anew[num++]=a[i];
        anew[num++]='#';
    }
    anew[num]='\0';
    //puts(anew);
}
int Manacher()
{
    init();
    int MAX=-1;
    int len=strlen(anew);
    //printf("%d\n",len);
    int id;//mx对应的回文串的对称轴所在的位置
    int mx=0;//当前访问到的所有回文子串，所能触及的最右一个字符的位置
    for(int i=1;i<len;i++)
    {
        if(i<mx)
            p[i]=min(p[2*id-i],mx-i);
        else
            p[i]=1;
        while(anew[i-p[i]]==anew[i+p[i]])//扩展
            p[i]++;
        if(mx<i+p[i])//最右的字符的位置要改变
        {
            id=i;
            mx=i+p[i];
        }
        MAX=max(MAX,p[i]-1);
    }
    return MAX;
}
int main()
{
    scanf("%s",a);
    printf("%d\n",Manacher());
    /*for(int i=1;i<strlen(anew);i++)
        printf("%d ",p[i]-1);
    printf("\n");*/
    return 0;
}

HDU 1686

题意：AZA AZAZAZA 输出3

解题思路：

if(j==plen)
{
    cnt++;
    j=Next[j];
}

HDU 2087

题意：aaaaaa aa 输出3

解题思路：

if(j==plen)
{
    cnt++;
    j=0;
}

HDU 3746

题意：给你一个字符串，要求将字符串的全部字符最少循环2次需要添加的字符数。

解题思路：找循环节。len-next[i]为此字符串的最小循环节(i为字符串的结尾)，如果len%(len-next[i])==0,此字符串的最小周期就为len/(len-next[i])。

int length=len-Next[len];//循环节长度
if(len!=length&&len%length==0)
    printf("0\n");
else printf("%d\n",length-Next[len]%length);

HDU 3336（存疑）

题意：求给出字符串的所有前缀在原字符串中出现的次数和。

解题思路：dp[i]代表以第i位结尾的字符串中包括多少以第i位字母结尾的前缀的出现次数，那么有dp[i]=dp[Next[i]]+1，利用Next数据跳转到第Next[i]的位置，这个位置的跟之前的有过多少次匹配，只要在原基础上加1即可。

HDU 2609

题意：有n个有01组成的字符串，每个字符串都代表一个项链，那么该字符串就是一个环状的结构，求可以经过循环旋转，最后不同的串有多少个。

解题思路：

将每个字符串转换成最小串（因为最小串对于每一个长度相同但不同的串都是不一样的），然后放在set里面去重。

最小表示法：

有一个字符串，这个字符串的首尾是连在一起的，要求寻找一个位置，以该位置为起点的字符串的字典序在所有的字符串中中最小。

假设有两个下标i，j，表示如果从i和从j出发的字符串，有一个k表示字符串的长度，如果长度达到len，就表示找到最小的串。

s[i+k] == s[j+k]: k++

s[i+k]>s[j+k]: i=i+k+1 表示以i，到i+k为起点的字符串，都不是最小字符串的前缀。

s[i+k]<s[j+k]: j=j+k+1 同理

直到i或j大于串长，找较小者。

注意：1.i和j一定是不同的。2.每次不等时，需要设置k为0。

复杂度：$O(n)$。

最小表示法模板

int findMin()
{
    int len=str.size();
    int i=0,j=1,k=0;
    while(i<len&&j<len&&k<len)
    {
        if(str[(i+k)%len]==str[(j+k)%len])
            k++;
        else if(str[(i+k)%len]>str[(j+k)%len])   //最大表示法这里变成<
        {
            i=i+k+1;
            k=0;
        }
        else
        {
            j=j+k+1;
            k=0;
        }
        if(i==j)j++;
    }
    return min(i,j);   //返回的是第一个最小串的首字符的位置
}

HDU 4513

题意：求最长回文子串，而外要求:从回文串最中间向两边满足非递增。

解题思路：改变一下扩展条件即可。

        while(anew[i-p[i]]==anew[i+p[i]])//扩展
        {
            if(anew[i-p[i]]!=-2)
            {
                if(anew[i+p[i]]<=anew[i+p[i]-2])p[i]++;
                else break;
            }
            p[i]++;
        }

HDU 3294

字符串转化的时候不用刚开始就转化，要判断好回文以后输出的地方再转化，否则会TLE。

2018年全国多校算法寒假训练营练习比赛（第五场）C

题意：有一个字符串，让你找到这个字符串 S 里面的子串T，必须满足是这个串的前缀，也是这个串的后缀，并且在字符串中也出现过一次的，输出最长满足要求字符串。

思路：利用Next数组，next数组表示的是这个串最长的公共前后缀，那么求出这个串所有的公共前后缀就是循环即可，因为最长的公共前后缀是next[len]，那么比它短一点的肯定是在这个前缀的最长前后缀，即next[next[len]]，然后KMP一下如果出现次数大于等于3的话就符合要求。