#include <bits/stdc++.h>
using namespace std;
vector <int> kmp(string &a, string &b) {
string s = b + '#' + a;
int n = s.length();
vector <int> p(n);
p[0] = 0;
for(int i = 1; i < n; i++) {
int j = p[i - 1];
while(j > 0 && s[i] != s[j]) {
j = p[j - 1];
}
if(s[i] == s[j]) {
j++;
}
p[i] = j;
}
vector <int> q(a.length());
for(int i = 0; i < (int)a.length(); i++) {
q[i] = p[i + (int)b.length() + 1];
}
return q;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
string a, b;
cin >> a >> b;
int m = a.length();
int n = b.length();
vector<vector<int>> p(m, vector<int>(n));
for(int i = 0; i < m; i++) {
string temp;
for(int j = i; j < m; j++) temp += a[j];
p[i] = kmp(b, temp);
}
int ans = 0;
pair <int, int> pos = {-1, -1};
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(p[i][j] > ans) {
ans = p[i][j];
pos = {i, j - p[i][j] + 1};
}
int x = p[i][j];
if(x > 0 && i + x < m && j - x >= 0) {
if(p[i + x][j - x] + p[i][j] > ans) {
ans = p[i + x][j - x] + p[i][j];
pos = {i, j - ans + 1};
}
}
}
}
// repeat entire procedure after reversing a
reverse(a.begin(), a.end());
for(int i = 0; i < m; i++) {
string temp;
for(int j = i; j < m; j++) temp += a[j];
// cout << temp << " ";
p[i] = kmp(b, temp);
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(p[i][j] > ans) {
ans = p[i][j];
int ind = i + p[i][j] - 1;
// cout << i << " " << j << ind << '\n';
pos = {m - ind - 1, j - p[i][j] + 1};
}
int x = p[i][j];
if(x > 0 && i + x < m && j - x >= 0) {
if(p[i + x][j - x] + p[i][j] > ans) {
ans = p[i + x][j - x] + p[i][j];
int ind = i + x + p[i + x][j - x] - 1;
// cout << i << " " << j << ind << '\n';
pos = {m - ind - 1, j - ans + 1};
}
}
}
}
cout << ans << '\n';
cout << pos.first << " " << pos.second << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
209 ms |
35732 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
