Cod sursa(job #1998707)

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

char A[2000001],B[2000001];
int n,m;
int urm[2000001];
vector <int> V;

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,2000001);
f.getline(B,2000001);

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)
    {
        V.push_back(i-m+1);

        x=urm[x];
    }
}
g<<V.size()<<'\n';
for(int i=0;i<V.size();++i)
    g<<V[i]<<" ";
return 0;
}