Seekthe Name, Seek the Fame

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 845 字

KMP跳border链输出所有公共前后缀长

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1458
// 题意：每行一个字符串（读到 EOF），输出一行所有既是其前缀又是其后缀的子串长度，递增排列。
// 思路：求前缀函数后从 n 沿 nxt 链一直跳到 0，链上每个值都是一组公共前后缀长度，倒序输出即递增。
// 复杂度：O(单串长度) 时间 / O(单串长度) 空间
// 易错点：答案要包含串自身长度 n；用栈/数组收集后反向输出，直接正序打印会得到递减序列。
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    while(cin>>s){
        int n=(int)s.size();
        vector<int> nxt(n+1,0);
        for(int i=1;i<n;i++){
            int j=nxt[i];
            while(j>0&&s[i]!=s[j]) j=nxt[j];
            if(s[i]==s[j]) j++;
            nxt[i+1]=j;
        }
        vector<int> out;
        for(int x=n;x>0;x=nxt[x]) out.push_back(x);
        for(int i=(int)out.size()-1;i>=0;i--){
            if(i!=(int)out.size()-1) cout<<' ';
            cout<<out[i];
        }
        cout<<'\n';
    }
    return 0;
}

Seekthe Name, Seek the Fame

正文

一本通·提高篇的其它内容