Cod sursa(job #1349920)

Utilizator alexmarMarinescu Alexandru alexmar Data 20 februarie 2015 16:00:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include<fstream>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

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

void construpi(){
int i,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()
{
    int i,k;
    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;}
    }
    fout<<c<<"\n";
    c=min(c,1000);
    for(i=1;i<=c;i++)fout<<d[i]<<" ";
    return 0;
}