#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T a,Args... args) {cout<<a<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define SZ(x) int(x.size())
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
vector<int> prefix_function(string &s) {
int n = s.size();
vector<int> pf(n);
pf[0] = 0;
for (int i = 1, j = 0; i < n; i++) {
while (j && s[i] != s[j]) j = pf[j-1];
if (s[i] == s[j]) j++;
pf[i] = j;
}
return pf;
}
vector<int> kmp(string &s, string &p) {
int n = s.size(), m = p.size(), cnt = 0;
vector<int> mx(n, 0);
if(!m)return mx;
vector<int> pf = prefix_function(p);
for(int i = 0, j = 0; i < n; i++) {
while(j && s[i] != p[j]) j = pf[j-1];
if(s[i] == p[j]) j++;
mx[i] = j;
if(j == m) {
cnt++;
j = pf[j-1];
}
}
return mx;
}
int ans, a, b;
void go(string &s, string &t, bool f = false){
int n = s.size();
int m = t.size();
string rev = t;
reverse(rev.begin(), rev.end());
forn(i, 0, n){
string lf = s.substr(0, i);
string rg = s.substr(i, n-i);
reverse(lf.begin(), lf.end());
vector<int> suf = kmp(rev, lf);
vector<int> pref = kmp(t, rg);
reverse(suf.begin(), suf.end());
forn(j, 0, m){
if(pref[j] + j < m){
int aux = pref[j] + suf[j+1];
if(ans < aux){
ans = aux;
if(f){
a = m - i - pref[j];
b = j - pref[j] - 1;;
}else{
a = i - suf[j+1];
b = j - pref[j] + 1;
}
}
}
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
string s, t;
cin >> s >> t;
go(s, t);
reverse(t.begin(), t.end());
go(s, t, true);
cout << ans << endl;
cout << a << " " << b << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
