데이터 구조의 문자열 - 문자열 일치 (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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.