KMP

kmp
周期

#include<iostream>

using namespace std;
const int N = 1000010;
char s[N];
int Next[N];
int n;
void get_next(){
    int j = 0;
    for(int i=2;i<=n;i++){
        while(j&&s[i]!=s[j+1]) j = Next[j];
        if(s[i]==s[j+1]) j++;
        Next[i] = j;
    }
}

int main(){
    int C = 0;
    while(scanf("%d",&n),n){
        C++;
        scanf("%s",s+1);
        get_next();
        
        cout<<"Test case #"<<C<<endl;
        for(int i= 1;i<=n;i++){
            int t = i-Next[i];
            
            if(t!=i&&i%t==0) cout<<i<<" "<<i/t<<endl;
        }
        cout<<endl;
    }
}

最短回文串
next数组可以得到前缀和后缀中相同的长度有多少，然后将回文串反转和不反转拼接起来

class Solution {
    
public:
    string shortestPalindrome(string s) {
        if(!s.size()) return "";
        
        string rv = s;
        reverse(rv.begin(),rv.end());
        string str = s + "#" + rv +"#";
        vector<int> next = get(str);
        int idx = next[str.size()-1];

        int n = str.size();
        string res = str.substr(n/2,s.size()-idx) + s;

        return res;
    }
    vector<int> get(string s){
        int n = s.size();
        s = "#" + s;
        vector<int> next(n+1);
        for(int  i=2,j=0;i<=n;i++){
            while(j&&s[j+1]!=s[i]) j = next[j];
            if(s[j+1]==s[i]) j++;
            next[i] = j;
        }
        return next; 
    }
};