Cod sursa(job #931550)

Utilizator mazaandreiAndrei Mazareanu mazaandrei Data 28 martie 2013 12:26:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
#include<cstring>
using namespace std;
char a[2000005];
char b[2000005];
int n,m,nr,poz[1005],p[2000005],k;
ifstream in("strmatch.in"); ofstream out("strmatch.out");
int main(){
    in.getline(a,2000005); in.getline(b,2000005);
    n=strlen(a); m=strlen(b);
    p[0]=-1;
    for(int i=1;i<n;++i){
        while(k && a[i]!=a[k]) k=p[k-1];
        if(a[k]==a[i]) ++k;
        p[i]=k;
    }
    k=0;
    for(int i=0;i<m;++i){
        while(k && b[i]!=a[k]) k=p[k-1];
        if(b[i]==a[k]) ++k;
        if(k==n){
            if(nr<1000) poz[nr]=i-n+1;
            nr++; k=p[k-1];
        }
    }
    out<<nr<<'\n';
    for(int i=0;i<min(nr,1000);++i) out<<poz[i]<<" ";
    out<<'\n';
    return 0;
}