Pagini recente » Cod sursa (job #1268846) | Cod sursa (job #1540490) | Cod sursa (job #2255926) | Cod sursa (job #2812202) | Cod sursa (job #1300298)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("potriveala.in");
ofstream fout("potriveala.out");
const int NMAX=250005;
const int XMAS=500005;
char a[NMAX],b[NMAX],bp[NMAX],c[XMAS];
int lena,lenb,lenbp,lenc,sol;
int z[XMAS],zs[XMAS];
inline void Rev()
{
int i,aux;
aux=lena>>1;
for (i=1;i<=aux;i++) swap(a[i],a[lena-i+1]);
aux=lenbp>>1;
for (i=1;i<=aux;i++) swap(bp[i],bp[lenbp-i+1]);
}
inline void ZALG(int *A,char *B,char *C,int len1,int len2)
{
int i,lt,rt,p;
//formam sirul
for (i=1;i<=len2;i++) c[i]=C[i];
c[len2+1]='#';
for (i=1;i<=len1;i++) c[len2+1+i]=B[i];
lenc=len1+len2+1;
lt=rt=0;
for (i=2;i<=lenc;i++)
if (i>rt)
{
lt=rt=i;
while (rt<=lenc && c[rt]==c[rt-i+1]) rt++;
rt--;
A[i]=rt-i+1;
}
else
{
p=i-lt+1;
if (A[p]<(rt-i+1)) A[i]=A[p];
else
{
lt=i;rt++;
while (rt<=lenc && c[rt]==c[rt-i+1]) rt++;
rt--;
A[i]=rt-i+1;
}
}
for (i=len2+2;i<=lenc;i++)
sol=max(sol,A[i]);
}
int main()
{
int i,j;
fin>>(a+1);
lena=strlen(a+1);
fin>>(b+1);
lenb=lenbp=strlen(b+1);
for (i=1;i<=lenb;i++) bp[i]=b[i];
for (i=lenb+1,j=1;i<=lena;i++,j++)
{
if (j==(lenb+1)) j=1;
b[i]=b[j];
}
lenb=max(lenb,lena);
Rev();
ZALG(zs,a,bp,lena,lenbp);
Rev();
ZALG(z,a,b,lena,lenb);
//impreuna
for (i=lenb+3,j=lenbp+lena+1;i<=lenc;i++,j--)
sol=max(sol,z[i]+zs[j]);
fout<<sol<<"\n";
return 0;
}