[BZOJ 1355]Radio Transmission

danihao123 posted @ 2016年3月05日 21:04 in 题解 with tags KMP bzoj BOI 循环节问题 , 193 阅读
转载请注明出处: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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter