Cod sursa(job #600979)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 4 iulie 2011 15:42:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <string>

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

string a, b;
int u[2000000], n, m, i, k, sol[1001], poz=0;

void prefix()
{
    u[1]=0;
    k=0;
    for (i=2; i<n; i++)
    {
        while (k>0 && a[k+1]!=a[i]) k=u[k];
        if (a[k+1]==a[i]) k++;
        u[i]=k;
    }
}

int kmp()
{
    k=0;
    for (i=1; i<m; i++)
    {
        while (k>0 && a[k+1]!=b[i]) k=u[k];
        if (a[k+1]==b[i]) k++;
        if (k==n-1)
        {
            poz++;
            sol[poz]=i-n+1;
            if (poz==1001) return 0;
            k=u[k];
        }
    }
    return 0;
}

int main()
{
    f >> a >> b;
    a=" "+a;
    b=" "+b;
    n=a.length();
    m=b.length();
    prefix();
    kmp();
    g << poz << "\n";
    for (i=1; i<=poz; i++)
        g << sol[i] << " ";
    return 0;
}