Cod sursa(job #2550724)

Utilizator bogosanuAndrei Bogos bogosanu Data 19 februarie 2020 08:44:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char T[N],P[N];
int a[N]; ///memoram pozitiile in a
int urm[N];
int n,m,k;

void citire()
{fin>>P>>T;
 n=strlen(P);
 m=strlen(T);
}


void prefix()
{int j=0;
 for(int i=1;i<n;++i)
    {while(j>0 && P[i]!=P[j])
           j=urm[j-1];
     if(P[i]==P[j])
        j++;
     urm[i]=j;
    }
}

void kmp()
{int q=0;
 for(int i=0;i<m;++i)
    {while(q>0 && P[q]!=T[i])
           q=urm[q-1];
     if(T[i]==P[q])
        q++;
     if(q==n)
        a[k++]=i-n+1;
    }

}


int main()
{citire();
 prefix();
 kmp();
 fout<<k<<"\n";
 if(k>1000) k=1000;
 for(int i=0;i<k;++i)
     fout<<a[i]<<" ";


    return 0;
}