Pagini recente » Borderou de evaluare (job #565513) | Cod sursa (job #352659) | Cod sursa (job #3161225) | Cod sursa (job #676450) | Cod sursa (job #2416911)
#include <bits/stdc++.h>
#define maxN 2 * 2000002
#define SIGMA 300
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];
int frq[maxN], Nxt[maxN];
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[2][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[0][i].nr[0] = P[i];
L[0][i].nr[1] = i + cnt < N ? P[i + cnt] : (N + 1);
L[0][i].id = i;
}
for (int t = 0; t < 2; ++ t)
{
memset(frq, 0, sizeof(frq));
memset(Nxt, 0, sizeof(Nxt));
for (int i = 0; i < N; ++ i)
++ frq[L[t][i].nr[!t]];
for (int i = 1; i <= N + 1; ++ i)
frq[i] += frq[i - 1];
for (int i = 0; i < N; ++ i)
{
int val = L[t][i].nr[!t];
if (val)
L[!t][frq[val - 1] + Nxt[val]] = L[t][i];
else
L[!t][Nxt[val]] = L[t][i];
++ Nxt[val];
}
}
P[L[0][0].id] = 0;
for (int i = 1; i < N; ++ i)
if (L[0][i - 1].nr[0] == L[0][i].nr[0] && L[0][i].nr[1] == L[0][i - 1].nr[1])
P[L[0][i].id] = P[L[0][i - 1].id];
else P[L[0][i].id] = i;
}
for (int i = 0; i < N; ++ i)
invSuf[L[0][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[0][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[0][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;
}