Cod sursa(job #1644830)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 10 martie 2016 09:45:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <cstring>
#define NMAX 200005

using namespace std;

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

int i, n, m, k, p[NMAX], ans[NMAX], cont = 0;
char a[NMAX], b[NMAX];

void make_prefix()
{
    k = 0;

    for (i = 2; i <= n; ++ i)
    {
        while (k > 0 && a[k + 1] != a[i])
            k = p[k];

        if (a[k + 1] == a[i])
            k ++;

        p[i] = k;
    }
}

int main()
{
    f.getline(a + 1, NMAX - 3);
    f.getline(b + 1, NMAX - 3);
    n = strlen(a + 1);
    m = strlen(b + 1);

    make_prefix();

    k = 0;

    for (i = 1; i <= m; ++ i)
    {
        while (k && a[k + 1] != b[i])
            k = p[k];

        if (a[k + 1] == b[i])
            k ++;

        if (k == n)
        {
            if (cont < 1000)
                ans[++ cont] = i - n;

            k = p[k];
        }
    }

    g << cont << '\n';

    for (i = 1; i <= cont; ++ i)
        g << ans[i] << " ";
    return 0;
}