Cod sursa(job #2416896)

Utilizator akaprosAna Kapros akapros Data 28 aprilie 2019 15:27:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <bits/stdc++.h>
#define maxN 2 * 2000002
#define SIGMA 2560

using namespace std;

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

int n, m;
char s[maxN], pat[maxN / 2];

struct Entry
{
    int nr[2], id;
    bool operator < (const Entry &ot) const
    {
        if (nr[0] == ot.nr[0] && nr[1] == ot.nr[1])
            return id < ot.id;
        if (nr[0] == ot.nr[0])
            return nr[1] < ot.nr[1];
        return nr[0] < ot.nr[0];
    }
} L[maxN];
int N;
int P[maxN], lcp[maxN], invSuf[maxN];

int ans[maxN];


void suffixArray()
{
    for (int i = 0; i < N; ++ i)
        P[i] = s[i];
    for (int stp = 1, cnt = 1; (cnt >> 1) < N; ++ stp, cnt <<= 1)
    {
        for (int i = 0; i < N; ++ i)
        {
            L[i].nr[0] = P[i];
            L[i].nr[1] = i + cnt < N ? P[i + cnt] : (SIGMA);
            L[i].id = i;
        }
        sort(L, L + N);

        P[L[0].id] = 0;
        for (int i = 1; i < N; ++ i)
            if (L[i - 1].nr[0] == L[i].nr[0] && L[i].nr[1] == L[i - 1].nr[1])
                P[L[i].id] = P[L[i - 1].id];
            else P[L[i].id] = i;
    }
    for (int i = 0; i < N; ++ i)
        invSuf[L[i].id] = i;
}
void compLcp()
{
    int k = 0;
    for (int i = 0; i < N; ++ i)
    {
        if (invSuf[i] == N - 1)
        {
            k = 0;
            continue;
        }
        int j = L[invSuf[i] + 1].id;
        while (i + k < N && j + k < N && s[i + k] == s[j + k])
            ++ k;
        lcp[invSuf[i]] = k;
        if (k > 0) -- k;
    }
}
int firstOcc(int x)
{
    while (x > 0 && lcp[x - 1] >= m)
        -- x;
    return x;
}
int main()
{
    scanf("%s\n%s", pat, s);
    n = strlen(s);
    s[n ++] = SIGMA;
    m = strlen(pat);
    for (int i = n; i < n + m; ++ i) s[i] = pat[i - n];
    N = n + m;
    suffixArray();
    compLcp();
    int lst = firstOcc(invSuf[n]), lim = invSuf[n];
    printf("%d\n", invSuf[n] - lst);
    for (int i = lst; i < lim; ++ i)
        ans[++ ans[0]] = L[i].id;
    sort(ans + 1, ans + ans[0] + 1);
    for (int i = 1; i <= min(ans[0], 1000); ++ i)
        printf("%d ", ans[i]);
    return 0;
}