Cod sursa(job #1159030)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 29 martie 2014 11:34:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <cstring>

using namespace std;

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

char a[2000010], b[2000010], c[2000010];

int n,m,k,sol[2000010],p[200010],i,q;

int main () {

    fin>>(b);
    fin>>(a);

    m=strlen(b);
    n=strlen(a);

    strcpy (c,a);
    strcpy(a+1,c);
    strcpy (c,b);
    strcpy (b+1,c);

    p[1]=0;

    for (i=2;i<=m;i++) {
        q=p[i-1];
        while (b[i]!=b[q+1] && q!=0)
            q=p[q];
        if (b[i]==b[q+1])
            p[i]=q+1;
        else
            p[i]=0;
    }

    q=0;

    for (i=1;i<=n;i++) {
        while (a[i]!=b[q+1] && q!=0)
            q=p[q];
        if (a[i]==b[q+1])
            q++;
        if (q==m) {
            sol[++k]=i-m;
            q=p[q];
        }
    }
    fout<<k<<"\n";
    k=min(k,1000);
    for (i=1;i<=k;i++)
        fout<<sol[i]<<" ";

    return 0;
}