码迷,mobileinhere.cn
首页 > 其他好文 > 详细

bzoj 1355---radio transmission(kmp)

时间:2018-07-31 19:33:11      阅读:11      评论:0      收藏:0      [点我收藏+]

标签:span   alt   pac   can   cst   name   inf   image   \n   

传送门

技术分享图片

由于我们知道kmp中的p[n](有的是next)存的是最长的长度,因此我们只需要将n-p[n]便可......

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cstdlib>
 7 using namespace std;
 8 int p[1000005],n;
 9 char st[1000005];
10 void pre()
11 {
12     int j=0;
13     p[0]=0;
14     for (int i=1; i<=n; i++){
15         while (j>0 && st[j+1]!=st[i+1]) j=p[j];
16         if (st[j+1]==st[i+1]) j++;
17         p[i+1]=j;
18     }
19 }
20 int main()
21 {
22     scanf("%d\n",&n);
23     cin>>st+1;
24     pre();
25     printf("%d\n",n-p[n]);
26     return 0;
27 }

miao~~~

 

 

bzoj 1355---radio transmission(kmp)

标签:span   alt   pac   can   cst   name   inf   image   \n   

原文地址:www.cnblogs.com/wangyh1008/p/9396948.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
2014 mobileinhere.cn 版权所有 京icp备13008772号-2
华人娱乐注册