알고스팟 - 접두사/접미사 (NAMING) [C++]

 이 문제는 KMP 알고리즘의 PI 배열을 이용하여 풀 수 있는 문제이다. 제한 시간이 500ms로 매우 짧고, 문자열 최대 길이가 40만이므로 반드시 O(N) 이하로 연산이 이루어져야 한다.

 

 이 문제의 핵심 아이디어는 k 다음으로 긴 접미사를 찾을 때 pi[k - 1]을 이용하면 된다는 것이다. 이 점만 알면 쉽게 풀리는 문제였다.

 

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

using namespace std;

vector<int> getPi(const string &input) {
	int m = input.size();

	vector<int> pi(m, 0);

	int begin = 1, matched = 0;

	while (begin + matched < m) {
		if (input[begin + matched] == input[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;

			continue;
		}

		if (matched == 0) {
			begin++;
			continue;
		}

		begin += matched - pi[matched - 1];
		matched = pi[matched - 1];
	}

	return pi;
}

vector<int> solve(const string &input) {
	vector<int> pi = getPi(input);
	vector<int> result;

	int k = input.size();

	while (k > 0) {
		result.push_back(k);
		k = pi[k - 1];
	}

	sort(result.begin(), result.end());

	return result;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	string father, mother;
	cin >> father;
	cin >> mother;

	string input = father + mother;

	vector<int> answers = solve(input);

	for (int ans : answers) {
		cout << ans << " ";
	}
	cout << '\n';

	return 0;
}