Cod sursa(job #1804008)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 12 noiembrie 2016 09:42:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

char p[2000001],t[2000001];
int urm[2000001],n,m,a[1001];

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;
    }
    /*for (q=1;q<=m;q++)
        cout<<urm[q]<<' ';
    cout<<'\n';*/
}

void kmp()
{
    int q,k=0,nr=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) {
                //g<<q-m+1<<' ';
                a[++nr]=q-m+1;
            }
            //cout<<k<<' ';
        }
        g<<nr<<'\n';
        for (q=1;q<=1000 && q<=nr;q++)
            g<<a[q]<<' ';
}

int main()
{
f.getline(p,2000001);
f.getline(t,2000001);
n=strlen(t);
m=strlen(p);
prefix();
kmp();
    return 0;
}