Submission #896887

#	Time	Username	Problem	Language	Result	Execution time	Memory
896887		classic	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	132 ms	572 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;
	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 = index2 - kmpSuffix[lengthStr1 + lengthStr2 - index1 - index2];
			}
		}
	}
	std::cout << maxLength << '\n';
	std::cout << positionPrefix.first << ' ' << positionPrefix.second;
	return 0;
}

• Subtask 1: 0 / 15