Cod sursa(job #1382441)

Utilizator mariusadamMarius Adam mariusadam Data 9 martie 2015 00:10:06
Problema Potrivirea sirurilor Scor 100
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");

int pi[2000002],d[2000002];
char x[2000002],y[2000002];
int n,m,nr,nrp;

void construct_pi(){
    int 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(){
    int 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;
}