Cod sursa(job #1300298)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 24 decembrie 2014 12:18:08
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#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;
}