Cod sursa(job #877998)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 13 februarie 2013 18:10:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream>
#include<string.h>
#define dim 2000008
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");
char N[dim],M[dim];
int n,m,k,q,p[dim],ans[1024],nr,i;
int main () {

    f>>(N+1);
    f>>(M+1);

    //prefix
    n=strlen(N+1);
    m=strlen(M+1);

    k=0;
    p[1]=0;

    for(i=2;i<=n;++i){

        while( k>0 && N[k+1]!=N[i] ){
            k=p[k];
        }

        if(N[k+1]==N[i])
            ++k;
        p[i]=k;
    }

    q=0;

    for(i=1;i<=m;++i){

        while(q>0 && N[q+1]!=M[i]){
            q=p[q];
        }
        if(N[q+1]==M[i])
            ++q;
        if(q==n){
            if(nr<=1000){
                ans[++nr]=i-q;
            }
        }
     }
     g<<nr<<"\n";
     for(i=1;i<=nr;++i)
        g<<ans[i]<<" ";
    return 0;
}