Cod sursa(job #1382201)

Utilizator mariusadamMarius Adam mariusadam Data 8 martie 2015 16:20:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <cstring>

using namespace std;

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

long pi[200002],d[200002];
char x[200002],y[200002];
long n,m,nr,nrp;

void construct_pi(){
    long k,i;
    k=0;
    pi[1]=0;
    for (i=2;i<=n;i++){
        while (k!=0&&x[i]!=x[k+1])
            k=pi[k];
        if (x[i]==x[k+1])
            k++;
        pi[i]=k;
    }
}

int main(){
    long k,i;
    r>>x+1;
    r>>y+1;
    n=strlen(x+1);
    m=strlen(y+1);
    construct_pi();
    k=0;
    for (i=1;i<=m;i++){
        while (k!=0 && y[i]!=x[k+1])
            k=pi[k];
        if (y[i]=x[k+1])
            k++;
        d[i]=k;
        if (k==n)
            nrp++;

    }
    w<<nrp<<"\n";
    nr=0;
        for (i=1;i<=m;i++)
            if (d[i]==n){
                w<<i-n<<" ";
                nr++;
                if (nr==1000)
                    break;
            }
    r.close();
    w.close();
    return 0;
}