sw 3143. 가장 빠른 문자열 타이핑

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_65wkqsb4DFAWS

SW Expert Academy

 

그냥 naive하게 짜면 시간 초과가 발생하므로 KMP를 활용하려고 하였다.

그런데 문제점은 

abababa 에서 aba를 찾으면 스킵이라 할때

첫번째 aba에서 다음 비교시에는 aba의 a는 j = table[j]에 의해 스킵되고 b부터 비교하게 된다.

하지만 문제는 aba를 찾았으면 다음 인덱스에서 aba를 다시 비교하기를 원한다.

따라서 j = table[j]가 아닌 j = 0 으로 초기화 해주고 해결했는데, 만약 겹치는게 하나도 없으면 parentSize만큼 어차피 

클릭이벤트를 수행해야한다. 발견했을 경우에는 패턴의 길이만큼 parentSize에서 빼주고 +1 의 작업을 수행한 뒤 

그 남은 값을 출력하면 된다.

 

naive방식은 전체에서 공통부분을 빼고 남은 것을 출력하는 방식이 아니라 idx와 함께 ans도 같이 증가시키는 작업이 들어가서 10000글자 짜리 string의 경우 시간초과 발생하는 것 같다.

 

#include<iostream>
#include<string>
#include<vector>
using namespace std;

string str1, str2;

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[i] != str[j])
		{
			j = table[j - 1];
		}
		if (str[i] == str[j])
		{
			table[i] = ++j;
		}
	}
	return table;
}

int KMP(string parent, string pattern)
{
	int parentSize = parent.size();
	int ans = parentSize;
	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)
			{
				j = 0;
				ans -= patternSize;
				ans++;
			}
			else
			{
				++j;
			}
		}
	}
	return ans;
}




int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> str1 >> str2;
		
		cout << "#" << test_case << " " << KMP(str1, str2) << endl;

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}