absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] [-9] 546E
[破碎的状态] [-7] BZOJ 1367

[破碎的状态] [-9] Hdu 2087

absi2011 posted @ Jul 13, 2016 09:24:52 PM in 刷题记录 with tags 小高考 HDU KMP AC自动机 , 562 阅读

这是一道kmp的模版题

这是一个中文题..

做法:直接kmp

感觉kmp直接用AC自动机的理解姿势..果然写起来好简单啊

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[10005];
char b[10005];
int fail[10005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    for (;;)
    {
        scanf("%s",a);
        if (a[0]=='#') break;
        scanf("%s",b);
        int i;
        fail[0]=-1;
        for (i=1;b[i]!='\0';i++)
        {
            int t=fail[i-1];
            for (;;)
            {
                if (t==-1) break;
                if (b[t+1]==b[i])
                {
                    break;
                }
                t=fail[t];
            }
            if (b[t+1]==b[i])
            {
                t++;
            }
            fail[i]=t;
        }
        int n=i;
        int now=-1;
        int sum=0;
        for (i=0;a[i]!='\0';i++)
        {
            for (;;)
            {
                if (now==-1) break;
                if (b[now+1]==a[i])
                {
                    break;
                }
                now=fail[now];
            }
            if (b[now+1]==a[i])
            {
                now++;
            }
            if (now==n-1)
            {
                sum++;
                now=-1;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

登录 *


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