Pagini recente » Cod sursa (job #842860) | Cod sursa (job #794068) | Cod sursa (job #2934095) | Cod sursa (job #2633862) | Cod sursa (job #2416896)
#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;
}