Cod sursa(job #1211300)

Utilizator tdr_drtTdr Drt tdr_drt Data 22 iulie 2014 12:35:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000001],b[2000001];
int pi[2000001];
int k,n,m,i;
int c[1005],nr;
int main(){
    f.getline(a,2000001); n=strlen(a);
    f.getline(b,2000001); m=strlen(b);
    for(i=1;i<n;i++){
        while(k>0&&a[k]!=a[i]) k=pi[k-1];
        if(a[k]==a[i]) k++;
        pi[i]=k;
    }
    k=0;
    for(i=0;i<m;i++){
        while(k>0&&a[k]!=b[i]) k=pi[k-1];
        if(a[k]==b[i]) k++;
        if(k==n){
            if(nr<1000) c[++nr]=i-n+1;
            else ++nr;
        }
    }
    g<<nr<<"\n";
    for(i=1;i<=min(nr,1000);i++) g<<c[i]<<" ";
    return 0;
}