KMP模板

//KMP算法模板
#include<iostream>
#include<cstring>

using namespace std;

char s[1005],str[105];
int Next[105];

void Get_KMP()
{
    int m = strlen(str);
    int i=0,j=-1;
    Next[0] = -1;
    while(i<m)
    {
        if(j == -1 || str[i] == str[j])
        {
            ++i;++j;
            //Next[i] = j;
            Next[i] = (str[i]!=str[j])?j:Next[j];
        }
        else 
        {
            j = Next[j];
        }
    }
    return ;
}

int KMP()
{
    int n = strlen(s);
    int m = strlen(str);
    int i=0, j=0;
    while(j<m && i<n)
    {
        if(j == -1 || s[i] == str[j])
        {
            i++;j++;
        }
        else
        {
            j = Next[j];
        }
        
    }
    if(j>=m) return i-m;
    else return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> s >> str;
    Get_KMP();
    printf("%d
",KMP());
    return 0;
}

//exKMP模板
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e4 + 10;
int Next[MAXN],extend[MAXN];
string str,s;

void Get_Next()
{
    int now = 0;
    Next[0] = str.size();
    while(str[now]==str[1+now] && now+1<str.size()) now++;
    Next[1] = now;
    int p0 = 1;
    for(int i=2; i<str.size(); i++)
    {
        if(Next[i-p0] + i < p0 + Next[p0]) Next[i] = Next[i - p0];
        else 
        {
            now = extend[p0] + p0 - i;
            now = max(now, 0);
            while(str[now]==str[i+now] && now+i<str.size()) now++;
            Next[i] = now;
            p0 = i;
        }
    }
}

void exKMP()
{
    Get_Next();
    int now = 0;
    while(str[now]==s[now] && now<s.size() && now<str.size()) now++;
    extend[0] = now;
    int p0 = 0;
    for(int i=1; i<s.size(); i++)
    {
        if(Next[i-p0] + i < p0 + extend[p0]) extend[i] = Next[i-p0];
        else 
        {
            now = extend[p0] + p0 -i;
            now = max(now, 0);
            while(str[now]==s[i+now] && now<str.size() && (i+now)<s.size()) now++;
            extend[i] = now;
            p0 = i;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> s >> str;
    exKMP();
    for(int i=0; i<str.size(); i++) 
    {
        if(i==str.size()-1) cout<<Next[i]<<endl;
        else cout<<Next[i]<<' ';
    }
    for(int i=0; i<s.size(); i++)
    {
        if(i==s.size()-1) cout<<extend[i]<<endl;
        else cout<<extend[i]<<' ';
    }
    return 0;
}

//manacher模板
#include<iostream>
#include<cstring>

using namespace std;

const int MAXN = 22e6 + 10;
int hw[MAXN];
char s[MAXN],str[MAXN/2];

void change()
{
    s[0] = s[1] = '#';
    int n = strlen(str);
    for(int i=1; i<=n; i++)
    {
        s[i*2] = str[i-1];
        s[i*2+1] = '#';
    }
    s[n*2+2] = 0;
}

void manacher()
{
    change();
    int maxright=0,mid;
    int n = strlen(s);
    for(int i=1; i<n; i++)
    {
        if(i<maxright)
            hw[i] = min(hw[mid*2-i], hw[mid]+mid-i);
        else 
            hw[i] = 1;
        for(;s[hw[i]+i]==s[i-hw[i]];hw[i]++);
        if(i+hw[i]>maxright)
        {
            maxright = i + hw[i];
            mid = i;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> str;
    manacher();
    int ans = 0;
    int n = strlen(s);
    for(int i=2; i<n; i++)
    {
        if(hw[i] > ans) ans = hw[i];
    }
    cout<< ans-1 <<endl;
    return 0;
}