Cod sursa(job #1803994)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 12 noiembrie 2016 09:28:05
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

char p[101],t[101];
int urm[101],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 && nr<1000;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<=nr;q++)
            g<<a[q]<<' ';
}

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