Cod sursa(job #562093)

Utilizator SadmannCornigeanu Calin Sadmann Data 22 martie 2011 11:55:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<cstring>
#define NMAX 2000005
using namespace std;

char A[NMAX],B[NMAX];
int NA,NB;
int poz[1020];
int pi[NMAX];

ifstream in("strmatch.in");
ofstream out("strmatch.out");

inline void make_prefix()
{
    int i,q=0;
    for(i=2,pi[1]=0;i<=NA;i++)
    {
        while(q && A[q+1]!=A[i])
            q=pi[q];
        if(A[q+1]==A[i])
            q++;
        pi[i]=q;
    }
}

int main()
{
    int i,q=0,nr=0;
    in>>A>>B;
    NA=strlen(A);
    NB=strlen(B);
    for(i=NA;i;i--)
        A[i]=A[i-1];
    A[0]=' ';
    for(i=NB;i;i--)
        B[i]=B[i-1];
    B[0]=' ';

    make_prefix();
    for(i=1;i<=NB;i++)
    {
        while(q && A[q+1]!=B[i])
            q=pi[q];
        if(A[q+1]==B[i])
            ++q;
        if(q==NA)
        {
            q=pi[NA];
            ++nr;
            if(nr<=1000)
                poz[nr]=i-NA;
        }

    }

    out<<nr<<"\n";
    for(i=1;i<=(nr<=1000?nr:1000);i++)
        out<<poz[i]<<' ';
    out<<"\n";


    return 0;
}