Cod sursa(job #1827505)

Utilizator akaprosAna Kapros akapros Data 11 decembrie 2016 21:25:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
#include <bits/stdc++.h>
#define maxN 2000002
#define maxA 1001
using namespace std;
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);

int n, m, v[maxA + 2], z[maxN], ans;
char a[maxN], b[maxN];
void read()
{
    gets(a + 1);
    gets(b + 1);
}
void zpref()
{
    int k, j, L = 0, R = 0;
    n = strlen(a + 1);
    for (k = 2; k <= n; ++ k)
    {
        if (k > R)
        {
            for (j = 1; a[j] == a[k + j - 1] && j <= n && (k + j - 1) <= n; ++ j)
                ++ z[k];
            L = k;
            R = k + z[k] - 1;
        }
        else
        {
            int K = k - L + 1;
            if (z[K] < R - k + 1)
                z[k] = z[K];
            else
            {
                int q = R + 1;
                while (a[q] == a[q - k + 1] && q <= n)
                    ++ q;
                z[k] = q - k;
                R = q - 1;
                L = k;
            }
        }
    }
}
void get_ans()
{
    int k, j, L = 0, R = 0, Z = 0, r;
    bool ok = 1;
    m = strlen(b + 1);
    for (k = 1; k <= n; ++ k)
        if (a[k] != b[k])
        {
            ok = 0;
            break;
        }
    if (ok)
    {
        ++ ans;
        if (v[0] < maxN)
            v[++ v[0]] = 1;
    }
    for (k = 2; k <= m; ++ k)
    {
        r = R;
        Z = 0;
        if (k > R)
        {
            for (j = 1; a[j] == b[k + j - 1] && j <= n && (k + j - 1) <= m; ++ j)
                ++ Z;
            L = k;
            R = k + Z - 1;
        }
        else
        {
            int K = k - L + 1;
            if (z[K] < R - k + 1)
                Z = z[K];
            else
            {
                int q = R + 1;
                while (b[q] == a[q - k + 1] && q <= m && (q - k + 1) <= n)
                    ++ q;
                Z = q - k;
                R = q - 1;
                L = k;
            }
        }
        if (R - L + 1 == n && R != r)
        {
            ++ ans;
            if (v[0] < maxA - 1)
                v[++ v[0]] = L;
        }
    }
}

void solve()
{
    zpref();
    get_ans();
}

void write()
{
    printf("%d\n", ans);
    for (int i = 1; i <= v[0]; ++ i)
        printf("%d ", v[i] - 1);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}