Pagini recente » Cod sursa (job #910127) | Cod sursa (job #1769496) | Cod sursa (job #1956277) | Cod sursa (job #813105) | Cod sursa (job #2118700)
#include <bits/stdc++.h>
using namespace std;
ifstream f("potriveala.in");
ofstream g("potriveala.out");
const int MAXN = 250010;
bool viz[MAXN];
int pi[MAXN];
int main(){
string a, b;
f >> b >> a;
a = ' ' + a;
b = ' ' + b;
pi[1] = 0;
int q = 0;
for(int i = 2; i < a.size(); ++i){
while(q && a[q+1] != a[i]) q = pi[q];
if(a[q+1] == a[i]) ++ q;
pi[i] = q;
}
q = 0;
for(int i = 1; i < b.size(); ++i){
while(q && a[q+1] != b[i]) q = pi[q];
if(a[q+1] == b[i]) ++ q;
if(q == a.size()-1){
q = pi[q];
viz[i-a.size()+3] ^= 1;
}
}
int best = 0;
for(int i = 1; i < b.size(); ++i){
if(viz[i]){
viz[i] ^= 1;
int j = i;
int k = i;
while(viz[j + a.size() - 1] && j + a.size() - 1 < b.size()){
j += a.size() - 1;
viz[j] ^= 1;
}
j += a.size() - 2;
int jj = j;
while(b[k-2] == a[a.size() - (i-k+1)] && k > 2 && (i- k + 1) < a.size()) --k;
while(b[j+1] == a[j+1-jj + 1] && j < b.size() - 1) ++j;
j = min(j, (int)(b.size() - 1));
best = max(best, j - k + 1);
}
}
g << best;
return 0;
}