POJ-2752-Seek the Name, Seek the

Seek the Name, Seek the Fame

题意：

• 当子字符串是主子符串（给出的字符串的前K个字符）的前缀与后缀时子字符串的长度

思路：

• nxt数组存的是该失配字符的前一个字符在前面出现过的最近一次失配的字符后面的一个字符的位置（返回失配字符前x个字符为后缀，[0 ~ x-1]个字符为前缀的后一个字符的位置）(失配字符的前x个字符与[0 ~ x-1]个字符相同)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int M=400010;
char s[M];
int nxt[M];
priority_queue <int,vector<int>,greater<int> >qu;
void getnext(int len)
{
    int j=0;
    int k=-1;
    nxt[0]=-1;
    while(j<len)
    {
        if(k==-1||s[j]==s[k])
        {
            j++;
            k++;
            nxt[j]=k;
        }
        else
        {
            k=nxt[k];//窗口移动
        }
        
    }
}
int main( )
{
    while(~scanf("%s",s))
    {
        while(!qu.empty( ))
        {
            qu.pop( );
        }
        int len=strlen(s);
        getnext(len);
        qu.push(len);
        int k=len;
        while(nxt[k]>0)
        {
            qu.push(nxt[k]);
            k=nxt[k];
        }
        int flag=0;
        while(!qu.empty( ))
        {
            if(flag==0)
            {
                printf("%d",qu.top( ));
                flag=1;
            }
            else
            {
                 printf(" %d",qu.top( ));
            }
            qu.pop( );
        }
        printf("\n");
    }
    return 0;
}