BOJ 16916 부분 문자열

www.acmicpc.net/problem/16916

 

와 이렇게 못된 문제는 처음이다. 내가 짠 코드가 시간초과가 계속 나길래 다른 사람 코드를 봤다. 그런데, 차이가 없는거다! 세상에! 그래서 하나하나 따져보기 시작했다. string의 size를 구하는 과정에서 났을까... 아니면 어디서 났을까... 하면서 매우 쫀쫀하게 짜보았다. cin.tie(0), cout.tie(0) 이런것도 썼다. 한번도 쓴 적이 없는데! 와!

뭐 어쨌든... 결론은 인덱스 0을 무시하면 시간초과가 나지 않았다는거다. 솔직히 좀 어이가 없긴 한데, 그렇다. ans[0]을 size 초기화해주면 시간 초과가 난다. 물론 그게 불필요한건 아는데(어차피 0일 테니까), 나를 화나게 한다. 만약 이 문제 풀거면 풀기 전에 화를 가라앉히길 바란다.

#include <iostream>
#include <vector>

using namespace std;


vector<int> failure(string P, int psize)
{
	vector<int> ans(psize);
	for (int i = 1, j = 0; i < psize; ++i)
	{
		while (j > 0 && P[i] != P[j])
		{
			j = ans[j - 1];
		}
		if (P[i] == P[j])
		{
			ans[i] = ++j;
		}
	}
	return ans;
}


int kmp(string str, string pat, int psize, int ssize)
{
	vector<int> f = failure(pat, psize);
	int j = 0;
	for (int i = 0; i < ssize; ++i)
	{
		while (j > 0 && str[i] != pat[j])
		{
			j = f[j - 1];
		}
		if (str[i] == pat[j])
		{
			if (j == psize - 1)
			{
				//return i - psize + 1;
				return 1;
			}
			else
				++j;
		}
	}
	return 0;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	string P, S;
	cin >> S >> P;
	int ans = kmp(S, P, P.size(), S.size());
	cout << ans;
	return 0;
}