对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串
对输入的串做一遍KMP，答案就是$n-nxt_n$
这个结论貌似挺容易推出来的吧
#include <bits/stdc++.h> using namespace std ; #define N 1000010 int n , m ; int nxt[ N ] ; char s[ N ] ; int main() { scanf( "%d" , &n ) ; scanf( "%s" , s + 1 ) ; int k = 0 ; for( int i = 2 ; i <= n ; i ++ ) { while( s[ k + 1 ] != s[ i ] && k ) k = nxt[ k ] ; if( s[ k + 1 ] == s[ i ] ) k ++ ; nxt[ i ] = k ; } printf( "%d\n" , n - nxt[ n ] ) ; }
BZOJ1355: [Baltic2009]Radio Transmission KMP
原文：https://www.cnblogs.com/henry-1202/p/9819676.html