字符串算法

manacher算法

char org[maxn],S[maxn];
int p[maxn];
inline int manacher()
{
    S[0]='$'; S[1]='#';
    int len=2;
    int L=strlen(org);
    for(int i=0;i<L;i++)
    {
        S[len++]=org[i];
        S[len++]='#';
    }
    S[len]='@';
    S[len+1]=0;
    int ri=0,id;
    for(int i=1;i<len;i++)
    {
        if(ri>i) p[i]=min(p[2*id-i],ri-i);
        else p[i]=1;
        while(S[i+p[i]]==S[i-p[i]]) p[i]++;
        if(i+p[i]>ri) { ri=i+p[i]; id=i; }
    }
    return len-1;
}

GetMax和GetMin算法

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iterator>
#include<stack>
using namespace std;
const int INF=1e9+7;
const int eps=0.0000001;
typedef __int64 LL;
int GetMax(const string& S)  
{
    int len=S.length();
    int a=0,b=1,k=0;
    while(a+k<len&&b+k<len)
    {
        if(S[a+k]==S[b+k]) k++;
        else
        {
            if(S[a+k]>S[b+k]) a=a+k+1;
            else b=b+k+1;
            k=0;
            if(a==b) b++;
        }

    }
    return min(a,b);
}
int GetMin(const string& S)
{
    int len=S.length();
    int a=0,b=1,k=0;
    while(a+k<len&&b+k<len)
    {
        if(S[a+k]==S[b+k]) k++;
        else
        {
            if(S[a+k]<S[b+k])  a=a+k+1;
            else  b=b+k+1;
            k=0;
            if(a==b) b++;
        }
    }
    return min(a,b);
}
int main()
{
    return 0;
}

KMP算法

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
void GetFail(char *P,int *fail)
{
    int L=strlen(P);
    fail[0]=fail[1]=0;
    for(int i=1;i<L;i++)
    {
        int j=fail[i];
        while(j&&P[i]!=P[j]) j=fail[j];
        fail[i+1]=(P[i]==P[j]?j+1:0);
    }
}
void KMP(char *T,char *P,int *fail)
{
    int L1=strlen(T);
    int L2=strlen(P);
    GetFail(P,fail);
    int j=0;
    for(int i=0;i<L1;i++)
    {
        while(j&&T[i]!=P[j]) j=fail[j];
        if(T[i]==P[j]) j++;
        if(j==L2) printf("%d
",i-L2+1);
    }
}
int main()
{
    char T[30],P[20];
    int fail[30];
    while(scanf("%s%s",T,P)!=EOF)
    {
        KMP(T,P,fail);
    }
    return 0;
}