Cod sursa(job #1552545)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 18 decembrie 2015 11:17:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <cstring>

using namespace std;

char a[2000010], b[2000010];
int phi[2000010], Phi[2000010], rez[1024];

int main ()
{
    freopen ("strmatch.in", "r", stdin);
    freopen ("strmatch.out", "w", stdout);

    gets (b + 1);
    gets (a + 1);

    int m = strlen (b + 1), n = strlen (a + 1);
    for (int i = 2; i <= m; ++i)
    {
        int k = phi[i - 1];
        while (k && b[i] != b[k + 1])
            k = phi[k];

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

    b[m + 1] = ' ';
    int p = 0;
    for (int i = 1; i <= n; ++i)
    {
        int k = Phi[i - 1];
        while (k && a[i] != b[k + 1])
            k = phi[k];

        if (a[i] == b[k + 1]) Phi[i] = k + 1;
        if (Phi[i] == m)
        {
            ++p;
            if (p <= 1000) rez[p] = i - m;
        }
    }

    printf ("%d\n", p);
    for (int i = 1; i <= p; ++i)
        printf ("%d ", rez[i]);

    printf ("\n");

    return 0;
}