Cod sursa(job #1678637)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 7 aprilie 2016 14:31:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#define NMAX 2000005
#define lim 1000

using namespace std;

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

int i, n, m, j, k = 0, pi[NMAX], ans[lim + 3], cnt = 0, sol[lim + 3];
char a[NMAX], b[NMAX];

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

    for (i = n; i >= 1; -- i)
        a[i] = a[i - 1];

    f.getline(b, NMAX - 3);
    m = strlen(b);

    for (i = m; i >= 1; -- i)
        b[i] = b[i - 1];

    pi[1] = 0;

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

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

        pi[i] = k;
    }

    k = 0;

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

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

        if (k == n)
        {
            ++ cnt;

            if (cnt <= lim)
                ans[cnt] = i - n;
            k = pi[k];
        }
    }

    g << cnt << '\n';

    for (i = 1; i<= min(1000, cnt); ++ i)
        g << ans[i] << " ";
    return 0;
}