Cod sursa(job #2278911)

Utilizator vladsirbu23Vlad Sirbu vladsirbu23 Data 8 noiembrie 2018 18:07:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string N,M;
int D[2000010],n,j,i,m,q,rez[2000010],k=0;
int main()
{
    fin>>N>>M;
    n=N.size();
    j=-1;
    D[0]=-1;
    for(i=1; i<n; i++)
    {
        while(j>-1&&N[j+1]!=N[i])
            j=D[j];
        if(N[j+1]==N[i])
            j++;
        D[i]=j;
    }

    m=M.size();
    q=-1;
    for(i=0; i<m&&k<=1000; i++)
    {
        while(q>-1&&N[q+1]!=M[i])
            q=D[q];
        if(N[q+1]==M[i])
            q++;
        if(q==n-1)
        {
            k++;
            rez[k]=i-n+1;
        }

    }
    fout<<k<<'\n';
    for(i=1;i<=k;i++)
    {
        fout<<rez[i]<<' ';
    }
}