Cod sursa(job #1206521)

Utilizator TibixbAndrei Tiberiu Tibixb Data 10 iulie 2014 13:24:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
#include<cstring>
using namespace std;
int n, m, p[200003], i, q, k, sol[1001];
char a[2000003], b[2000003];
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main(){
        in>>a+1;
        n=strlen(a+1);
        in>>b+1;
        m=strlen(b+1);
        q=0;
        p[1]=0;
        for(i=2; i<=n; i++){
            while(a[i]!=a[q+1] && q!=0)
                q=p[q];
            if(a[i]==a[q+1])
                q++;
            p[i]=q;
        }
        q=0;
        for(i=1; i<=m; i++){
            while(b[i]!=a[q+1] && q!=0)
                q=p[q];
            if(b[i]==a[q+1])
                q++;
            if(q==n){
                k++;
                if(k<=1000)
                    sol[k]=i-n;
                q=p[q];
            }
        }
        if(k>1000)
            k=1000;
        out<<k<<"\n";
        for(i=1; i<=k; i++)
            out<<sol[i]<<" ";
return 0;
}