Cod sursa(job #1129139)

Utilizator alexmarMarinescu Alexandru alexmar Data 27 februarie 2014 20:23:34
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include<fstream>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int n,m,i,k,c,pi[2000001],d[2000001];
char x[2000001],y[2000001];

void construpi(){
k=0;
for(i=1;i<n;i++){
    while(k>0&&x[i]!=x[k])k=pi[k-1];
    if(x[i]==x[k])k++;pi[i]=k;
}

}

int main()
{
    fin>>x;
    fin>>y;
    n=strlen(x);
    m=strlen(y);
    construpi();
    k=0;
    for(i=0;i<m;i++){
        while(k>0&&y[i]!=x[k])k=pi[k-1];
        if(y[i]=x[k])k++;
        if(k==n){d[c]=i-n+1;c++;}
    }
    fout<<c<<"\n";
    c=min(c,1000);
    for(i=0;i<c;i++)fout<<d[i]<<" ";
    return 0;
}