POJ2752 Seek the Name, Seek the Fame

题目

前后缀的重合，很有KMP的感觉
next（或者pre）的妙用

最后输出答案用了递归

#include <string>
#include <iostream>
#define MAXN 400005
using namespace std;

string str;
int pre[MAXN];
int T;

void dfs(int size) {
    if(size==0) return;
    dfs(pre[size]);
    printf("%d ",size);
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    while( cin >> str ) {
        
        int size = str.length(); str = ‘ ‘ + str;
        pre[1] = 0; int len = 0; 
        for(int i=1;i<size;++i) {
            while(len&&str[i+1]!=str[len+1]) len = pre[len];
            if(str[i+1]==str[len+1]) len++;
            pre[i+1] = len;
        }

        dfs(size); puts("");
    }

}

POJ2752 Seek the Name, Seek the Fame

原文：https://www.cnblogs.com/Neworld1111/p/15150165.html