제출 #896892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
896892		classic	Necklace (Subtask 4) (BOI19_necklace4)	C++14	0 / 15	270 ms	560 KiB

necklace

#include <bits/stdc++.h>

namespace classic {
	// Knuth-Morris-Pratt
	std::vector<int> prefixFunction(std::string str) {
		int lengthStr = (int)str.size();
		std::vector<int> prefix(lengthStr);
		for (int index = 1; index < lengthStr; index++) {
			int previousIndex = prefix[index - 1];
			while (previousIndex > 0 && str[index] != str[previousIndex]) {
				previousIndex = prefix[previousIndex - 1];
			}
			if (str[index] == str[previousIndex]) {
				previousIndex++;
			}
			prefix[index] = previousIndex;
		}
		return prefix;
	}
} // namespace classic

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::string str1, str2;
	std::cin >> str1 >> str2;
	int lengthStr1 = str1.size(), lengthStr2 = str2.size();
	int maxLength = 0;
	std::pair<int, int> positionPrefix;
	std::function<void(bool)> turnedOver = [&](bool isTurnedOver) {
		for (int index1 = 0; index1 < lengthStr1; index1++) {
			std::string prefixStr1 = str1.substr(0, index1);
			std::string suffixStr1 = str1.substr(index1, lengthStr1 - index1);
			reverse(prefixStr1.begin(), prefixStr1.end());
			std::string reverseStr2(str2.begin(), str2.end());
			reverse(reverseStr2.begin(), reverseStr2.end());
			std::vector<int> kmpPrefix = classic::prefixFunction(prefixStr1 + '#' + str2);
			std::vector<int> kmpSuffix = classic::prefixFunction(suffixStr1 + '#' + reverseStr2);
			for (int index2 = 1; index2 <= lengthStr2; index2++) {
				int length = kmpPrefix[index1 + index2] + kmpSuffix[lengthStr1 + lengthStr2 - index1 - index2];
				if (maxLength < length) {
					maxLength = length;
					positionPrefix.first = index1 - kmpPrefix[index1 + index2];
					positionPrefix.second = (isTurnedOver ? lengthStr2 - index2 : index2) - kmpPrefix[lengthStr1 + lengthStr2 - index1 - index2];
				}
			}
		}
	};
	turnedOver(false);
	reverse(str2.begin(), str2.end());
	turnedOver(true);
	std::cout << maxLength << '\n';
	std::cout << positionPrefix.first << ' ' << positionPrefix.second;
	return 0;
}

• Subtask 1: 0 / 15