洛谷题单指南-字符串-P4391 [BOI2009] Radio Transmission 无线传输

原题链接：https://www.luogu.com.cn/problem/P4391

题意解读：s1由若干个s2组成，求s2的最小长度，注意题目中说明s1是子串，但是不影响，可以认为s1是补全的由若干s2组成的字符串。

解题思路：

设s1由x个s2组成，如图所示

设s1的Next数组从0开始，那么其最长相同前后缀长度为x-1个s2，即Next[s1.size()-1]，那么s2的长度即为s1.size() - Next[s1.size()-1]

100分代码：

#include <bits/stdc++.h>
using namespace std;

int n;
string s;
int Next[1000005];

int main()
{
    cin >> n >> 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];
}