Cod sursa(job #2330923)

Utilizator DavidLDavid Lauran DavidL Data 28 ianuarie 2019 22:58:55
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

const int NMAX = 2e6 + 5;
const int LOG = 30;

struct chestie
{
    int ord[2], poz;
};

bool cmp(chestie a, chestie b)
{
    if (a.ord[0] != b.ord[0])
        return a.ord[0] < b.ord[0];
    return a.ord[1] < b.ord[1];
}

int n, m;
int P[LOG][NMAX];
chestie L[NMAX];
int V[NMAX];
int pas, cnt;

bool ok(int poz)
{
    if (n - poz + 1 < m)
        return 0;

}

void getSuffixArray()
{
    for (int i = 1; i <= n; i++)
        P[0][i] = A[i] - '0';

    for (pas = 1, cnt = 1; (pas >> 1) < n; cnt++, pas <<= 1)
    {
        for (int i = 1; i <= n; i++)
        {
            L[i].ord[0] = P[cnt - 1][i];
            L[i].ord[1] = i + pas <= n ? P[cnt - 1][i + pas] : -1;
            L[i].poz = i;
        }
        sort(L + 1, L + n + 1, cmp);

        for (int i = 1; i <= n; i++)
        {
            if (i > 1 && L[i].ord[0] == L[i - 1].ord[0] && L[i].ord[1] == L[i - 1].ord[1])
                P[cnt][L[i].poz] = P[cnt][L[i - 1].poz];
            else
                P[cnt][L[i].poz] = i;
        }
    }
    cnt--;
}

int cauta(int cum)
{
    int st = 1, dr = n;
    if (cum == -1 && ok(V[st])) // cautam cel mai mic
        return st;
    else if (cum == 1 && ok(V[dr]))
        return dr;

    while (dr - st > 1)
    {
        int mij = (st + dr) / 2;
        int h = comp(V[mij]);
        if (h == -1) // M este mai mic
            dr = mij;
        else if (h == 1) // M este mai mare
            st = mij;
        else if (h == 0)
        {
            comp == -1 ? dr = mij : st = mij;
        }
    }
    cum == -1 ? return dr : return st;
}

int main()
{
    fi >> M + 1 >> A + 1;
    m = strlen(M + 1);
    n = strlen(A + 1);

    getSuffixArray();

    for (int i = 1; i <= n; i++)
        V[P[cnt][i]] = i;

    int st = cauta(-1), dr = cauta(1);

    fo << dr - st + 1 << "\n";
    for (int i = st; i <= dr; i++)
        fo << i - 1 << " ";

    return 0;
}