Cod sursa(job #1552526)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 18 decembrie 2015 11:07:01
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
# include <bits/stdc++.h>

using namespace std;

const int Nmax = 2000000 + 5;

int N, i, sol = 0, M, nr = 0;
int phi[Nmax], v[Nmax];
char a[Nmax], b[Nmax];

void PHI()
{
    int k;

    N = strlen(a+1);

    phi[1] = 0;

    for (i = 2; i <= N; i++)
    {
        k = phi[i - 1];

        while (k && a[i] != a[k+1])
            k = phi[k];

        if (a[i] == a[k + 1]) phi[i] = k + 1;
        else phi[i] = 0;
    }
}

void check()
{
    int k;
    M = strlen(b + 1);
    for (i = 1; i <= M; ++i)
    {
        k = v[i-1];

        while (k && b[i] != a[k+1])
            k = phi[k];

        if (b[i] == a[k+1]) v[i] = k + 1;
        else v[i] = 0;
    }

    for (i = 1; i <= M; ++i)
        if (v[i] == N - 1) sol++;

}

int main ()

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

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

    a[strlen(a+1) + 1] = ' ';

    PHI();

    check();

    printf("%d\n", sol);

    for (i = 1; i <= M && nr < 1000; ++i)
        if (v[i] == N-1) printf("%d ", i - (N - 1)), ++i;

    printf("\n");

    return 0;
}