데이터 구조의 문자열 - 문자열 일치 (kmp 알고리즘)

직렬 구조 연습 - 문자열 일치
Time Limit: 1000MS Memory limit: 65536K
제목 설명
  두 문자열 string 1 과 string 2 를 지정 하여 string 2 가 string 1 의 하위 문자열 인지 판단 합 니 다.
 
입력
 여러 그룹의 데 이 터 를 포함 하 는 것 을 입력 하 십시오. 각 그룹의 테스트 데 이 터 는 두 줄 을 포함 하고 첫 번 째 줄 은 string 1 을 대표 하 며 두 번 째 줄 은 string 2 를 대표 합 니 다. string 1 과 string 2 에서 빈 칸 이 나타 나 지 않도록 보장 합 니 다.
 
출력
 각 그룹의 입력 데이터 에 대해 string 2 가 string 1 의 하위 문자열 이면 "YES" 를 출력 합 니 다. 그렇지 않 으 면 "NO" 를 출력 합 니 다.
 
예제 입력

abc

a

123456

45

abc

ddd

예제 출력

YES

YES

NO

#include <iostream>

#include <string>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <stack>



using namespace std;



void GET_next(string t, int next[])

{

    int j, k;

    j=0; k=-1;

    next[0]=-1;

    int len=t.size();



    while(j<len )

    {

        if(k==-1 || t[j]==t[k] )

        {

            j++;

            k++;

            next[j]=k;

        }

        else

            k=next[k];

    }

}



int KMP(string s, string t, int next[] )

{

    int i, j;

    i=0; j=0;

    int len1=s.size();

    int len2=t.size();



    while(i<len1 && j<len2 )

    {

        if(j==-1 || s[i]==t[j] )

        {

            i++;

            j++;

        }

        else

            j=next[j];

    }

    if(j==len2 )

      cout<<"YES
";

    else

      cout<<"NO
";

    return 0;

}





int main()

{

    string s, t;

    int i, j;

    int len1, len2;

    int next[1000];



    while(cin>>s)

    {

        cin>>t;

        len1=s.size();

        len2=t.size();

        GET_next(t, next);

        KMP(s, t, next);

    }

    return 0;

}

 주석 화:

#include <iostream>

#include <string>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <stack>



using namespace std;



void GET_next(string t, int next[]) //  next   

{

    int j, k;

    j=0; //             

    k=-1;

    next[0]=-1;//       ，      1  ，     0  

    int len=t.size();



    while( j<len ) //t   

    {

        if(k==-1 || t[j]==t[k] )

        { //  k=-1，     

            j++;

            k++;   //k  ：t1 t2 t3...tk = t(j-k+1) t(j-k+2)...t(j-1)

                   //    

            next[j]=k; //next[  ]    

        }

        else

            k=next[k]; //k   

    }

    int i;

  /*for(i=0; i<len; i++)

    {

        cout<<next[i]<<" ";

    }

    cout<<endl; */



}

 /*   ：t ：a b a a b c a c

           ：0 1 2 3 4 5 6 7

       next:-1 0 0 1 1 2 0 1

 */

int KMP(string s, string t, int next[] )

{

    int i, j;

    i=0; j=0;

    int len1=s.size();

    int len2=t.size();

    //        

    while(i<len1 && j<len2 )// i     j    

    {

        if(j==-1 || s[i]==t[j] )

        { //  j=-1，（    ）     ，    -1   

          //      ，                

            i++;

            j++;

        }

        else//          

            j=next[j]; //      j  ， i    ，    

    }

    if(j==len2 ) //         j      len2，     

                 //           

      cout<<"YES
";

    else

      cout<<"NO
";

    return 0;

}



int main()

{

    string s, t;

    int i, j;

    int len1, len2;

    int next[1000];

    while(cin>>s) //    

    {

        cin>>t;//    

        len1=s.size(); //    

       // len2=t.size(); //    



        GET_next(s, next); //   t   next   

        //KMP(s, t, next);  //  next    kmp  

    }

    return 0;

}