题目vj链接

题面：

题意：
给定一个字符串 S S S，计算 S S S 中前缀和后缀相等的串在 S S S 中出现了多少次。
按照长度递增的顺序输出 S S S 中前缀和后缀相等的串在 S S S 中出现的次数。

题解：
先统计对于每一个前缀 S [ 1 , i ] S[1,i] S[1,i] 在 S S S 中出现了多少次，然后通过跳 n t [ i ] nt[i] nt[i]，找到前缀与后缀相等的串。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
//#define max(x,y) ((x)>(y)?(x):(y))
//#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=100100;

char a[maxn],b[maxn];
char str[maxn];
int nt[maxn];
int ans[maxn];

void dfs(int i,int cnt)
{
    if(i==0)
    {
        printf("%d\n",cnt);
        return ;
    }
    dfs(nt[i],cnt+1);
    printf("%d %d\n",i,ans[i]);
}

void get(void)
{
    int n=strlen(str+1);
    nt[1]=0;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j>0&&str[i]!=str[j+1]) j=nt[j];
        if(str[i]==str[j+1]) j++;
        nt[i]=j;
    }
    for(int i=n;i>=1;i--)
    {
        ans[i]+=1;
        ans[nt[i]]+=ans[i];
    }
    dfs(n,0);
}



int main(void)
{
    scanf("%s",str+1);
    get();
    return 0;
}