hihocoder #1015 KMP

4572 단어 code
#include<stdio.h>

#include<iostream>

#include<math.h>

#include<string.h>

using namespace std;

int n,m;//          

char a[1000001],b[100000];//              

int p[11111];//  next   

void getp()

{

    p[1]=0;

    int i,j=0;

    for(i=2;i<=m;i++)

    {

        while(j>0&&b[j+1]!=b[i]) j=p[j];

        if(b[j+1]==b[i]) j+=1;

        p[i]=j;

    }

}//     next 

int kmp()

{    

    int i,j=0,cnt=0;

    for(i=1;i<=n;i++)

    {

        while(j>0&&b[j+1]!=a[i]) j=p[j];

        if(b[j+1]==a[i]) j+=1;

        if(j==m){

            cnt++;

            j=p[j];

        }

    }

    return cnt;    

}//      kmp 

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        scanf("%s%s",b+1,a+1);

        m=strlen(b+1);

        n=strlen(a+1);

        getp(); 

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

        cout<<p[i]<<endl;

        cout<<kmp()<<endl;

    }

    return 0;

}//        

기왕 네가 KMP를 이렇게 NB로 배웠으니 차라리 나와 함께 요리를 배우는 것이 낫겠다. 아하하

좋은 웹페이지 즐겨찾기