Cod sursa(job #2038396)

Utilizator AlexTheDagonBogdan Tudor AlexTheDagon Data 13 octombrie 2017 17:34:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <string.h>
#include <fstream>
#define NM 2000005
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char c,H[NM],N[NM];
int n,h,f,S[NM],k,cnt,sol[NM];
int main()
{
    in>>N+1;
    n=strlen(N+1);
    S[0]=-1;
    S[1]=0;
    for(int i=2;i<=n;++i)
    {
        k=i-1;
        c=N[i];
        while(S[k]!=-1 && N[S[k]+1]!=c)k=S[k];
        S[i]=S[k]+1;
    }
    in>>H+1;
    h=strlen(H+1);
    for(int i=1;i<=h;++i)
    {
        while(f!=-1 && N[f+1]!=H[i])f=S[f];
        if(f==-1)f=0;
        else
        {
            ++f;
            if(f==n)
            {
                sol[++cnt]=i-n;
                f=S[f];
            }
        }
    }
    out<<cnt<<'\n';
    for(int i=1;i<=cnt;++i)out<<sol[i]<<" ";
    return 0;
}