#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 - kmpSuffix[lengthStr1 + lengthStr2 - index1 - index2] : index2 - kmpPrefix[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 |
270 ms |
808 KB |
Output is correct |
| 2 |
Correct |
224 ms |
560 KB |
Output is correct |
| 3 |
Correct |
292 ms |
572 KB |
Output is correct |
| 4 |
Correct |
217 ms |
568 KB |
Output is correct |
| 5 |
Correct |
199 ms |
572 KB |
Output is correct |
| 6 |
Correct |
199 ms |
580 KB |
Output is correct |
| 7 |
Correct |
206 ms |
348 KB |
Output is correct |
| 8 |
Correct |
242 ms |
560 KB |
Output is correct |
| 9 |
Correct |
241 ms |
828 KB |
Output is correct |
