Cod sursa(job #552382)

Utilizator alinabBlaj Alina alinab Data 12 martie 2011 10:52:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
//kmp
#include <fstream>
#include <string.h>
#include <stdio.h>

using namespace std;

char p[2000005], t[2000005];
int a[2000005], b[2000005], n, m, k=0;

void citire()
{
    freopen("strmatch.in", "r", stdin);
    scanf("%s", p);
    scanf("%s", t);
    m=strlen(p);
    n=strlen(t);
}

void kmp1()
{
    int i=0, j=-1;
    b[i]=j;
    while (i<m)
    {
        while (j>=0 && p[i]!=p[j])
            j=b[j];
        i++;
        j++;
        b[i]=j;
    }
}

void kmp2()
{
    int i=0, j=0;
    while (i<n)
    {
        while (j>=0 && t[i]!=p[j])
            j=b[j];
        i++;
        j++;
        if (j==m)
        {
            k++;
            a[k]=(i-j);
            j=b[j];
        }
    }
}

void afisare()
{
    freopen("strmatch.out","w",stdout);
    printf("%d\n", k);
    for(int i=1; i<=k && i<=1000; i++)
        printf("%d ",a[i]);
}

int main()
{
    citire();
    kmp1();
    kmp2();
    afisare();
    return 0;
}