題目大意：給出一個(gè)字符串，已知它是一個(gè)字符串S不斷反復(fù)后構(gòu)成的無限長(zhǎng)的字符串的一個(gè)子串，求S的最短長(zhǎng)度是多少。

思路：利用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; }

轉(zhuǎn)載于:https://www.cnblogs.com/lytwajue/p/6930312.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1355: [Baltic2009]Radio Transmission的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。