学步园

题意:

求字符串S的, 既是前缀串, 又是后缀串的子串.

思路:

next数组的应用.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 400005;
char s[MAXN];
int next[MAXN];
int stack[MAXN],top,n;
void prekmp()
{
    next[0] = -1;
    int j = -1;
    for(int i=1;s[i];i++)
    {
        while(j!=-1 && s[i]!=s[j+1])    j = next[j];
        if(s[i]==s[j+1])    j++;
        next[i] = j;
    }
}

int main()
{
    while(~scanf("%s",s))
    {
        prekmp();
        top = -1;
        n = strlen(s);
        int j = n-1;
        while(j!=-1)
        {
            stack[++top] = j+1;
            j = next[j];
        }
        while(top>0)
        {
            printf("%d ",stack[top--]);
        }
        printf("%d\n",stack[top]);
    }
}