#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) - kmpSuffix[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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
269 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
247 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
