Cod sursa(job #1565784)

Utilizator BugirosRobert Bugiros Data 11 ianuarie 2016 12:52:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <cstdio>
using namespace std;

const int MAXSIR = 2000005;
const int MAXSOL = 1003;

char a[MAXSIR],b[MAXSIR];
int n,m;

int prefix[MAXSIR];

int sol[MAXSOL];
int nrsol = 0;

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

void citire()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a + 1);
    gets(b + 1);
    n = 1;
    m = 1;
    while(a[n] != 0)
        ++n;
    --n;
    while(b[m] != 0)
        ++m;
    --m;
}

void kmp()
{
    int q = 0;
    for (int i = 1;i <= m;++i)
    {
        while(q != 0 && a[q + 1] != b[i])
            q = prefix[q];
        if (a[q + 1] == b[i])
            ++q;
        if (q == n)//potrivire
        {
            q = prefix[n];
            ++nrsol;
            if (nrsol <= 1000)
                sol[nrsol] = i - n;
        }
    }
}

void afisare()
{
    printf("%d\n",nrsol);
    int lim = nrsol;
    if (lim > 1000)
        lim = 1000;
    for (int i = 1;i <= lim;++i)
        printf("%d ",sol[i]);
    printf("\n");
}

int main()
{
    citire();
    creare_prefix();
    kmp();
    afisare();
    return 0;
}