字符串

前缀函数

std::vector<int> prefix_function(string s)
{
    int n=s.length();
    std::vector<int> pi(n);
    for (int i = 1; i < n; ++i)
    {
        int j=pi[i-1];
        while(j>0 && s[i]!=s[j])
        {
            j=pi[j-1];
        }
        if(s[i]==s[j])
        {
            j++;
        }
        pi[i]=j;
    }
    return pi;
}

KMP

std::vector<int> KMP(string find, string main)
{
    int size1=find.size();
    int size2=main.size();
    string cur=find+'#'+main;
    std::vector<int> v;
    std::vector<int> lps=prefix_function(cur);
    for (int i = size1; i <= size1+size2; ++i)
    {
        if(lps[i]==size1)
        {
            v.push_back(i-2*size1);
        }
    }
    return v;
}

Z函数

std::vector<int> Z(string s)
{
    int n=s.size();
    std::vector<int> z(n,0);
    for (int i = 1,l = 0,r = -1; i < n; ++i)
    {
        if(i+z[i-l]-1 < r)
        {
            z[i]=z[i-l];
        }
        else
        {
            z[i]=max(r-i+1,0);
            while(i+z[i]<n && s[z[i]]==s[i+z[i]])
            {
                z[i]++;
            }
            l=i,r=i+z[i]-1;
        }
    }
    return z;
}

Manacher算法

std::vector<int> Manacher(string s)
{
    int n=s.size();
    std::vector<int> d(n,0);
    for (int i = 0, j=0, l=0, r=-1; i < n; ++i)
    {
        j=l+r-i;
        if(i>r)
        {
            while(i-d[i]>=0 && i+d[i]<n && s[i-d[i]]==s[i+d[i]])
            {
                d[i]++;
            }
            l=i-d[i]+1,r=i+d[i]-1;
        }
        else if(j-d[j]>=l)
        {
            d[i]=d[j];
        }
        else
        {
            d[i]=j-l+1;
            while(i-d[i]>=0 && i+d[i]<n && s[i-d[i]]==s[i+d[i]])
            {
                d[i]++;
            }
            l=i-d[i]+1,r=i+d[i]-1;
        }
    }
    return d;
}