1213. [S/W 문제해결 기본] 3일차 - String

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14P0c6AAUCFAYi&categoryId=AV14P0c6AAUCFAYi&categoryType=CODE

SW Expert Academy

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

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

}

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


int main(int argc, char** argv)
{
	int test_case;
	for (test_case = 1; test_case <= 10; ++test_case)
	{
		int t;
		cin >> t;
		string pattern, parent;
		cin >> pattern >> parent;

		cout << "#"<<t << " " <<KMP(pattern, parent) << endl;

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