POJ2752 Seek the Name, Seek the Fame KMP经典 Next

给定字符串，输出所有相等的前后缀的长度。

首先容易想到Next[len2] 必然满足题目要求。

接下来的所有也满足的必然是s2[1 ~ Next[len2]]的前后缀，即是一个递归的过程。

char s1[1005], s2[400005];
int Next[400005];
int len1, len2;

void get_Next() {
    for (int i = 2, j = 0; i <= len2; i++) {
        while (s2[i] != s2[j + 1] && j > 0) j = Next[j];
        if (s2[i] == s2[j + 1]) Next[i] = ++j;
    }
}


int main() {
    while (~scanf("%s", s2 + 1)) {
        len2 = strlen(s2 + 1);
        memset(Next, 0, sizeof Next);
        vector<int> ans;
        get_Next();
        int tmp = len2;
        while (Next[tmp]) {
            ans.push_back(tmp);
            tmp = Next[tmp];
        }
        ans.push_back(tmp);
        sort(ans.begin(), ans.end());
        for (int i = 0; i < ans.size() - 1; i++) printf("%d ", ans[i]);
        printf("%d
", ans.back());
    }
}