【KMP】Radio Transmission

问题 L: 【KMP】Radio Transmission

题目描述

给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少。

输入

第一行给出字符串的长度L，第二行给出一个字符串，全由小写字母组成。

输出

输出最短的长度。

样例输入

8

cabcabca

样例输出

提示

我们可以利用abc不断自我连接得到abcabcabc，读入的cabcabca是它的子串。

对于全部数据，1≤L≤1e6

【题意】：

题意花里胡哨，其实就是问，最小循环串。

【题解】：

kmp的强大应用，可以利用最长前缀来处理该问题。

相关解释可以去b站搜索ACwing——字符串和哈希。

结论是：m-next[m] 最小循环串的长度。

 #include<bits/stdc++.h>

 using namespace std;

 const int N = 1e6+;

 char p[N];

 int Next[N],m;

 void get_Next(){

     for(int i=,j= ; i<=m ; i++ ){

         while( j && p[i] != p[j+] ) j = Next[j];

         if( p[i] == p[j+] ) j ++;

         Next[i] = j ;

     }

 }

 int main()

 {

     scanf("%d",&m);

     scanf("%s",p+);

     get_Next();

     /*

     for(int i=1;i<=m;i++){

         printf("%d%c",Next[i],i==m?'\n':' ');

     }

     */

     printf("%d\n",m-Next[m]);

     return ;

 }

巴特西

【KMP】Radio Transmission

问题 L: 【KMP】Radio Transmission

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章