Pagini recente » Cod sursa (job #864727) | Cod sursa (job #1355370) | Cod sursa (job #2688657) | Cod sursa (job #49443) | Cod sursa (job #2330923)
#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;
}