Cod sursa(job #1434686)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 11 mai 2015 09:27:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstring>
#include <cstdio>
#define lengmax 2000005
#define maxx 1000
char x[lengmax], y[lengmax];
int l[lengmax], apar[lengmax], p;
void build_lv()
{
    int k = 0;
    int n = strlen(x) - 1;
    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 k = 0;
    int n = strlen(x) - 1;
    int m = strlen(y) - 1;
    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) apar[++p] = i - n;
    }
    printf("%d\n", p);
    for(int i = 1; i<=minim(1000, p); i++)
        printf("%d ", apar[i]);

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

    gets(x + 1);
    x[0] = ' ';
    gets(y + 1);
    y[0] = ' ';
    build_lv();
    solve();
}