Cod sursa(job #2038409)

Utilizator KleinWolfPop Dan Andrei KleinWolf Data 13 octombrie 2017 17:41:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

ifstream in ("strmatch.in");
ofstream out ("strmatch.out");

char N[2000001],H[2000001],c;
int n,h,s[2000001],sol[1001],v;
int k,f;

int main()
{
    in>>N+1;
    n=strlen(N+1);
    ///se construieste S
    s[0]=-1;
    s[1]=0;
    for(int i=2;i<=n;i++)
    {
        ///se calculeaza s[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);
    f=0;
    for(int i=1;i<=h;i++)
    {
        while (f!=-1)
            if (N[f+1]==H[i])
                break;
            else f=s[f];
        if(f==-1)
            f=0;
        else
        {
            f++;
            if(f==n)
            {
                if(v<1000)
                {
                    v++;
                    sol[v]=i-n;
                }
                f=s[f];
            }
        }
    }
    out<<v<<endl;
    for(int i=1;i<=v;i++)
        out<<sol[i]<<" ";
}