Cod sursa(job #2025870)

Utilizator akaprosAna Kapros akapros Data 23 septembrie 2017 13:14:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>
#define maxN 2000002
#define maxS 1002

using namespace std;

FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);

/* ------------------------------------------------- */
int m, n;
char a[maxN], b[maxN];
/* ------------------------------------------------- */
int shift[maxN], bpos[maxN];
/* ------------------------------------------------- */
int ans[maxS];

void prepCase1() /// fullsuff
{
    // bposi = starting idx of border for suffi..n in pattern a
    int i = m, j = m + 1;
    bpos[i] = j;
    while (i > 0)
    {
        while (j <= m && a[i - 1] != a[j - 1])
        {
            if (!shift[j])
                shift[j] = j - i;
            j = bpos[j];
        }
        -- i;
        -- j;
        bpos[i] = j;
    }
}
void prepCase2()
{
    int j = bpos[0];

    for (int i = 0; i <= m; ++ i)
    {
        if (!shift[i])
            shift[i] = j;
        if (i == j)
            j = bpos[j];
    }
}

int main()
{
    scanf("%s\n%s", a, b);
    m = strlen(a);
    n = strlen(b);
    int s = 0;
    prepCase1();
    prepCase2();
    while (s <= n - m)
    {
        int j = m - 1;
        while (j >= 0 && a[j] == b[s + j])
            -- j;
        if (j < 0)
        {
            if (ans[0] < 1000)
                ans[++ ans[0]] = s;
            else
                ++ ans[0];
            s += shift[0];
        }
        else
            s += shift[j + 1];
    }
    printf("%d\n", ans[0]);
    for (int i = 1; i <= min(ans[0], 1000); ++ i)
        printf("%d ", ans[i]);
    return 0;
}