Cod sursa(job #1299964)

Utilizator catalinrebegeaUNIBUC-Claudia Catarig catalinrebegea Data 23 decembrie 2014 22:57:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <cstring>
#define Nmax 4000005

using namespace std;

char a[Nmax],b[Nmax];
int Z[Nmax],N,M,sol[Nmax];

inline void ZAlgorithm()
{
    int L=0,R=0,i,k;
    for(i=2;i<=N;++i)
        if(i>R)
        {
            L=i;
            for(R=i;R<=N && R-L+1<=M && a[R]==a[R-L+1];++R);
            --R;
            Z[i]=R-L+1;
        }
        else
        {
            k=i-L+1;
            if(Z[k]<R-i+1)
                Z[i]=Z[k];
            else
            {
                L=i; ++R;
                for(;R<=N && R-L+1<=M && a[R]==a[R-L+1];++R);
                --R;
                Z[i]=R-L+1;
            }
        }
}

inline void ConCat()
{
    for(int i=1;i<=M;++i)
        a[N+i]=b[i];
    N+=M;
}

int main()
{
    int i;
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    scanf("%s%s", (a+1),(b+1));
    N=strlen(a+1); M=strlen(b+1);
    ConCat();
    ZAlgorithm();

    for(i=N-M+1;i<=N;++i)
        if(Z[i]>=N-M)
            sol[++sol[0]]=i-(N-M)-1;
    printf("%d\n", sol[0]);
    for(i=1;i<=sol[0] && i<=1000;++i)
        printf("%d ", sol[i]);
    printf("\n");
    return 0;
}