Cod sursa(job #1808843)

Utilizator vladbatalanBatalan Vlad vladbatalan Data 18 noiembrie 2016 11:35:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstring>

using namespace std;

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

char A[2000010], B[2000010];
int q, prefix[2000010],LGa,LGb;
int n, poz[1024];

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

int main()
{
    fin>>A>>B;
    q=0;
    LGa=strlen(A);
    LGb=strlen(B);
    for(int i=LGa;i>0;i--)A[i]=A[i-1];A[0]='#';
    for(int i=LGb;i>0;i--)B[i]=B[i-1];B[0]='#';
    make_prefix();

    q=0;
    n=0;
    for(int i=1; i<=LGb; i++)
    {
        while(q>0 && A[q+1]!=B[i])
            q=prefix[q];
        if(A[q+1]==B[i])
            q++;
        if(q==LGa)
        {
            q=prefix[LGa];
            if(n<1000)
                poz[++n]=i-LGa;
        }
    }
    fout<<n<<'\n';

    for(int i=1; i<=n; i++)
    {
        fout<<poz[i];
        if(i!=n)
            fout<<' ';
    }
    return 0;
}