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

3749 단어 데이터 구조
직렬 구조 연습 - 문자열 일치
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; }

좋은 웹페이지 즐겨찾기