백분 16916번 부분문자열

문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

 

간단한 문제인데 브루트포스로 풀면 시간초과 이므로

이참에 KMP 알고리즘을 공부해봤다. 접미사 접두사 공통영역 제외하고, 다시 비교하는 알고리즘

 

ababbabc

abad

비교시 인덱스 3에서 d와 b가 달라서 끊기는 상황이라면 aba까지는 같은 상황이다

따라서 parent의 앞 aba를 뛰어넘고 그 다음인 b부터 다시 시작할수 도 있겠으나, b이후의 값을 모르는 상태이므로

만약 b이후가 ad라면 aba를 뛰어넘고 b부터 시작했을 떄 못찾는 문제 발생.

따라서 충돌지점 b ( pattern 입장에선 d) 바로 직전인 a로 부터 접두사와 일치되는 개수를 확인함 현재 1개

그렇다면 충돌 지점 바로 앞부터 1개는 pattern의 맨 앞 인덱스부터 1개랑 같으므로 그 인덱스에서 다시 시작하는 원리이다.

 

 

  

#include<iostream>
#include<vector>
#include<string>

using namespace std;



vector<int> makeTable(string str)
{
	int size = str.size();
	vector<int> table(size,0);
    
    int j = 0;
    for(int i = 1; i < size; i++)
    {
    	while(j > 0 && str[j] != str[i])
        {
        	j = table[j - 1];
        }
        
        if(str[j] == str[i])
        {
        	table[i] = ++j;
        }
    }
    
    return table;
}

int KMP(string parent, string pattern)
{
	int parentSize = parent.size();
    int patternSize = pattern.size();
    
    int j = 0;
    vector<int> table = makeTable(pattern);
    for(int i = 0; i < parentSize; i++)
    {
    	while(j > 0 && parent[i] != pattern[j])
        {
        	j = table[j-1];
        }
        if(parent[i] == pattern[j])
        {
 			if(j == patternSize - 1)
            {
            	return 1;
            }
            else
            {
            	j++;
            }
        }
        
    }
    
    return 0;
}

int main(void)
{
	string str1, str2;
    
    cin >> str1 >> str2;
    
   	int check = KMP(str1,str2);
    
}