BZOJ1355: [Baltic2009]Radio Transmission

题目大意：给出一个字符串，已知它是一个字符串S不断反复后构成的无限长的字符串的一个子串，求S的最短长度是多少。

思路：利用KMP算法，答案就是n-next[n].证明例如以下：

图太渣了。。。

另一种情况就是next[n]<=n/2,自己画。

总之就是原串能够被划分成S的后缀和若干段S，因此是合法答案；而KMP保证Next[n]尽量大，因此n-next[n]是最小答案。

代码：

#include <cstdio> #include <cstring> #include <cctype> #include <iostream> #include <algorithm> using namespace std;#define N 1000010 char s[N]; int nxt[N];int main() {int len;scanf("%d", &len);scanf("%s", s + 1);int i, j = 0;for(i = 2; i <= len; ++i) {while(j && s[j + 1] != s[i])j = nxt[j];if (s[j + 1] == s[i])++j;nxt[i] = j;}printf("%d",len-nxt[len]);return 0; }

转载于:https://www.cnblogs.com/lytwajue/p/6930312.html

总结

以上是生活随笔为你收集整理的BZOJ1355: [Baltic2009]Radio Transmission的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。