[C++] 광고(KMP) - 1305

KMP 알고리즘

---

1305번: 광고

가능한 광고의 길이중 가장 짧은 것의 길이를 출력

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


vector<int> makeTable(string pattern)
{
	vector<int> table(pattern.size(), 0);

	int head = 0;
	for (int tail = 1; tail < pattern.size(); tail++)
	{
		while (head > 0 && pattern[head] != pattern[tail])
			head = table[head - 1];

		if (pattern[head] == pattern[tail])
		{
			table[tail] = ++head;
		}
	}

	return table;
}

int main()
{
	int size;
	string pattern;

	cin >> size;
	cin >> pattern;

	vector<int> table = makeTable(pattern);
	cout << size - table[size - 1];

	return 0;
}

위 코드에서 주의깊게 봐야할 부분은

 

 

cout << size - table[size - 1];

이 코드입니다.

 

table은 접두사와 중복되는 문자의 위치와 중복의 길이를 담고 있습니다

따라서"광고판의 사이즈"에 

"광고판 끝에 위치한 문자가 담고 있는 중복되는 길이"를 뺴면

광고의 길이중 가장 짧은 것의 길이를 구할 수 있게 되는 겁니다.