Cod sursa(job #1374236)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 5 martie 2015 00:36:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <cstring>
#define Nmax 2000005
#define nmin 1005
using namespace std;
char x[Nmax], y[Nmax];
int l[Nmax], ap[Nmax], p;
void build_l()
{
    int n = strlen(x) - 1;
    int k = 0;
    l[1] = 0;
    for(int i = 2; i<=n; i++)
    {
            while(x[i] != x[k + 1] && k > 0)
                k = l[k];
            if(x[i] == x[k + 1]) k ++;
            l[i] = k;
    }
}
inline int minim(int a, int b)
{
    return a > b? b : a;
}
void solve()
{
    int n = strlen(x) - 1, m = strlen(y) - 1;
    int k = 0;
    for(int i = 1; i<=m; i++)
    {
        while(y[i] != x[k + 1] && k > 0)
            k = l[k];
        if(y[i] == x[k + 1]) k ++;
        if(k == n) ap[++ p] = i - n ;
    }
    printf("%d\n", p);
    for(int i = 1; i<=minim(p, 1000); ++i)
        printf("%d ", ap[i]);
}
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    gets(x + 1);
    x[0] = ' ';
    gets(y + 1);
    y[0] = ' ';
    build_l();
    solve();
}