526互联

E2. Erase and Extend (Hard Version)

发布时间 2023-08-22 17:17:20作者: 久远寺冇珠

 题意：给你一个字符串s，请你找到所有的特殊字符串，满足它既是s的前缀，又是s的后缀，并输出它在s中出现的次数。

 

 做法：对于第一步，我们只需要先做出kmp，考虑kmp中ne数组的意义，不就是求border吗，那么我们一直去求最后一个字符串字母的border，然后就能把所有的既是前缀又是后缀的字符串求出来了。然后下一步我们要求这玩意出现在字符串中的次数，考虑拓展kmp中z函数的意义，在求z函数的时候开一个数组cnt来记录该前缀对应出现的次数，然后就a了哈哈哈

#include <bits/stdc++.h>
using namespace std;
int ans[100010];
int ans1[100010];
void solve()
{
    string a;
    cin>>a;
    int n=a.size();
    vector<int>ne(n+1);
    for(int i=1,j=0;i<n;i++)
    {
        while(j&&a[j]!=a[i])j=ne[j-1];
        if(a[j]==a[i])j++;
        ne[i]=j;
    }
    int p=ne[n-1];
    while(p!=0)
    {
        ans[p]++;
        p=ne[p-1];
    }
    ans[n]++;
    vector<int>z(n+1);
    for(int i=1,l=0,r=0;i<n;i++)
    {
        if(z[i-l]<r-i+1)
            z[i]=z[i-l];
        else
        {
                z[i]=max(0,r-i+1);
                while(i+z[i]<n&&a[i+z[i]]==a[z[i]])z[i]++;
                l=i;
                r=i+z[i]-1;
        }
    }
    
    for(int i=0;i<n;i++)
    {
        ans1[z[i]]++;
    }
    ans1[n]++;
    for(int i=n-1;i>=1;i--)
    {
        ans1[i]+=ans1[i+1];
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(ans[i])cnt++;
    }
    cout<<cnt<<"\n";
    for(int i=1;i<=n;i++)
    {
        if(ans[i])
        cout<<i<<" "<<ans1[i]<<"\n";
    }

}
signed main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // int t = 1;
    // cin >> t;
    // while (t--)
    solve();
    return 0;
}