Cod sursa(job #1803993)

Utilizator KemyKoTeo Virghi KemyKo Data 12 noiembrie 2016 09:26:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

int urm[2000001],m,n,nr,l,u[1002];
char p[2000001],t[2000001];

void citire ()
{
    f.get(p,2000001);f.get();
    f.get(t,2000001);
    m=strlen(p);n=strlen(t);
}

void prefix ()
{
    int q,k;
    k=0;
    urm[1]=0;
    for(q=2;q<=m;q++)
    {
        while(k>0 && p[k]!=p[q-1])
            k=urm[k];
        if(p[k]==p[q-1])k++;
        urm[q]=k;
    }
}

void kmp ()
{
    int q,k;
    k=0;
    for(q=0;q<=n;q++)
    {
        while(k>0 && p[k]!=t[q])
            k=urm[k];
        if(p[k]==t[q])k++;
        if(k==m)
            {
                if (l<=999)
                {
                    l++;
                    u[l]=q-m+1;
                }
                nr++;
            }
    }
    g<<nr<<'\n';
}

int main()
{
    int i;
    citire();

    if(m>n)g<<0;
    else
    {
        prefix();
        kmp();
        for (i=1;i<=l;i++)
            g<<u[i]<<" ";
    }

return 0;
}