Cod sursa(job #2373253)

Utilizator akaprosAna Kapros akapros Data 7 martie 2019 12:52:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
#define maxN 2000002
#define maxS 1000

using namespace std;

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

int n, m;
char a[maxN], b[maxN];

int pi[maxN];

int sol[maxS + 2];

void pref()
{
    pi[0] = -1;
    int k = -1;
    for (int i = 1; i < n; ++ i)
    {
        while (k >= 0 && a[i] != a[k + 1])
            k = pi[k];
        if (a[i] == a[k + 1])
            ++ k;
        pi[i] = k;
    }
}
int main()
{
    scanf("%s\n", a);
    scanf("%s\n", b);
    n = strlen(a);
    m = strlen(b);
    pref();
    int k = -1, ans = 0;
    for (int i = 0; i < m; ++ i)
    {
        while (k >= 0 && b[i] != a[k + 1])
            k = pi[k];
        if (b[i] == a[k + 1])
            ++ k;

        if (k == n - 1 && ans < maxS)
            sol[ans ++] = i - n + 1;
            else
                if (k == n)
                ++ ans;
    }

    printf("%d\n", ans);
    for (int i = 0; i < maxS && i < ans; ++ i)
        printf("%d ", sol[i]);
    return 0;
}