Cod sursa(job #792754)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 29 septembrie 2012 19:04:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <cstring>

#define LGMAX 2000003

using namespace std;

FILE *inFile = fopen ("strmatch.in", "r");
FILE *outFile = fopen ("strmatch.out", "w");

int na;
int nb;
int pref[LGMAX];
int res[LGMAX];

char a[LGMAX];
char b[LGMAX];

void prefix()
{
    int i = 0;
    int j = -1;

    pref[i] = j;
    while (i < na)
    {
        while (j >= 0 && a[i] != a[j])
            j = pref[j];

        ++i;
        ++j;
        pref[i] = j;
    }
}

void kmp()
{
    int i = 0;
    int j = 0;

    while (i < nb)
    {
        while (j >= 0 && b[i] != a[j])
            j = pref[j];

        ++i;
        ++j;

        if (j == na)
        {
            res[++res[0]] = i - j;
            j = pref[j];
        }
    }
}

void result()
{
    fprintf (outFile, "%d\n", res[0]);

    if (res[0] > 1000)
        res[0] = 1000;

    for (int i = 1; i <= res[0]; ++i)
        fprintf (outFile, "%d ", res[i]);

    fprintf (outFile, "\n");
}

int main()
{
    fgets (a, LGMAX, inFile);
    fgets (b, LGMAX, inFile);

    na = strlen (a) - 1;
    nb = strlen (b) - 1;

    if (na > nb)
    {
        fprintf (outFile, "0\n");
        return 0;
    }

    prefix();
    kmp();
    result();

    return 0;
}