Cod sursa(job #1998711)

Utilizator dumitrescu_andreiDumitrescu Andrei dumitrescu_andrei Data 8 iulie 2017 20:46:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char A[2000005],B[2000005];
int n,m;
int urm[2000005];
int V[1024];
int w;

void urmatorul()
{
    int k=-1;
    urm[0]=0;

    for(int x=1;x<m;++x)
    {
        while(k>0 && A[k+1]!=A[x]) k=urm[k];
        if(A[k+1]==A[x]) k++;
        urm[x]=k;
    }


}

int main()
{ int x=-1;
f.getline(A,2000005);
f.getline(B,2000005);

n=strlen(B);
m=strlen(A);
urmatorul();
for(int i=0;i<n;++i)
{
    while(x>0 && A[x+1]!=B[i]) x=urm[x];
    if(A[x+1]==B[i]) x++;
    if(x==m-1)
    {
      ++w;
      if(w<=1000)
        V[w]=i-m+1;

        x=urm[x];
    }
}
g<<w<<'\n';
for(int i=1;i<=min(w,1000);++i)
    g<<V[i]<<" ";
return 0;
}