Cod sursa(job #1552553)

Utilizator andreinmAndrei andreinm Data 18 decembrie 2015 11:21:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <cstdio>
#include <cstring>
using namespace std;
int phi[2000005] , n , m , v[2000005];
char a[2000005] , b[2000005] ;
void make_phi (char a[2000005] , int n)
{
    int k;
    phi[1] = 0;
    for (int i = 2 ; i <= n ; ++i)
    {
        k = phi[i - 1];
        while (a[i] != a[k + 1] && k > 0)
            k = phi[k];
        if (a[i] == a[k + 1]) phi[i] = k + 1;
        else phi[i] = 0;
    }
}

void kmp (char a[2000005] , char b[2000005] , int v[2000005] , int n , int m)
{
    make_phi (a , n);
    int k;
    for (int i = 1 ; i <= m ; ++i)
    {
        k = v[i - 1];
        while (k > 0 && b[i] != a[k + 1])
            k = phi[k];
        if (b[i] == a[k + 1])
            v[i] = k + 1;
        else v[i] = 0;
    }
}
int main()
{
    freopen ("strmatch.in" , "r" , stdin);
    freopen ("strmatch.out" , "w" , stdout);
    gets (a + 1);
    gets (b + 1);
    n = strlen (a + 1);
    m = strlen (b + 1);
    a[n + 2] = '^';
    kmp (a , b , v , n , m);
    int nr = 0;
    for (int i = 1 ; i <= m ; ++i)
        if (v[i] == n) nr++;
    printf ("%d\n" , nr);
    nr = 0;
    for (int i = 1 ; i <= m ; ++i)
        if (v[i] == n && nr < 1000)
            printf("%d " , i-n) , nr++;

    return 0;
}