Cod sursa(job #2795342)

Utilizator nicuvladNicu Vlad nicuvlad Data 6 noiembrie 2021 11:31:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char P[N], T[N];
int a[N],urm[N],n,m,k;
void Prefix()
{
    int i,j=0;
    for(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(P[q]==T[i]) ++q;
        if(q==n)
        {
            a[k++]=i-n+1;
        }
    }
}
int main()
{
  fin.getline(P,N);///pattern
  fin.getline(T,N);///Text
  n=strlen(P);
  m=strlen(T);
  Prefix();
  KMP();
  fout<<k<<'\n';
  for(int i=0;i<k;i++)fout<<a[i]<<' ';

 return 0;
}