Cod sursa(job #1912369)

Utilizator duesakBourceanu Cristian duesak Data 8 martie 2017 06:16:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000001],B[2000001];
int Ap[2000001];
int v[1002];
int main(){
    int la,lb,i,j,nrs=0;
    bool b;
    fin.get(A,2000000);
    fin.get();
    fin.get(B,2000000);
    la=strlen(A);
    lb=strlen(B);
    j=0;
    for(i=1;i<la;i++){
        if(A[i]==A[j]){Ap[i]=j+1;++j;}
        else
        while(j){
            j=Ap[j-1];
        }
    }
    j=0;
    for(i=0;i<lb;i++){
        while(j&&A[j]!=B[i])j=Ap[j-1];
        if(A[j]==B[i])++j;
        if(j==la){
            ++nrs;
            if(nrs<=1000)v[nrs]=i+1-j;
            j=Ap[j-1];
            }
    }
    /*
    for(i=0;i<lb+1-la;i++){
        if(lb<la)break;
        b=true;
        for(j=0;j<la;j++)
            if(A[j]!=B[i+j]){b=false;break;}
        if(b)
            if(v[0]<1000)v[++v[0]]=i;
            else v[0]++;
    }
    */
    fout<<nrs<<'\n';
    for(i=1;i<=min(nrs,1000);i++)
        fout<<v[i]<<" ";
    fout<<'\n';
    fin.close();
    fout.close();
    return 0;
}