Radio Transmission 无线传输

利用 Next 数组求解字符串的最小循环节长度，若字符串长度为 n，则最小循环节长度 =n−Next[n−1]。

#include<bits/stdc++.h>
using namespace std;
int Next[1000001];
int main(){
    int n;cin>>n;
    string s;
    cin>>s;
    // 求Next数组
    for(int i=1,j=0;i<n;i++){
        while(j&&s[i]!=s[j])j=Next[j-1];
        if(s[i]==s[j])j++;
        Next[i]=j;
    }
    // 最小循环节
    cout<<n-Next[n-1];
    return 0;
}

时间复杂度：O(n) 空间复杂度：O(n)