[BZOJ 1355]Radio Transmission
转载请注明出处：http://danihao123.is-programmer.com/
KMP处女作……
然而这题只用得着失配函数= =
话说常见的OI考试中考KMP好像就只有考循环节问题的了= =
代码：
/**************************************************************
Problem: 1355
User: danihao123
Language: C++
Result: Accepted
Time:32 ms
Memory:5688 kb
****************************************************************/
#include <cstdio>
const int maxn=1000000+10;
char buf[maxn];
int f[maxn];
int main(){
int n;
register int i,j;
scanf("%d",&n);
scanf("%s",buf);
// f[0]=f[1]=0;
for(i=1;i<n;i++){
j=f[i];
while(j && buf[i]!=buf[j])
j=f[j];
if(buf[i]==buf[j])
f[i+1]=j+1;
else
f[i+1]=0;
}
printf("%d\n",n-f[n]);
return 0;
}
评论 (0)
