Pagini recente » Cod sursa (job #1992868) | Rating Ciocotisan Cosmin (Smoke12345) | Cod sursa (job #2163090) | Cod sursa (job #1760481) | Cod sursa (job #2025870)
#include <bits/stdc++.h>
#define maxN 2000002
#define maxS 1002
using namespace std;
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);
/* ------------------------------------------------- */
int m, n;
char a[maxN], b[maxN];
/* ------------------------------------------------- */
int shift[maxN], bpos[maxN];
/* ------------------------------------------------- */
int ans[maxS];
void prepCase1() /// fullsuff
{
// bposi = starting idx of border for suffi..n in pattern a
int i = m, j = m + 1;
bpos[i] = j;
while (i > 0)
{
while (j <= m && a[i - 1] != a[j - 1])
{
if (!shift[j])
shift[j] = j - i;
j = bpos[j];
}
-- i;
-- j;
bpos[i] = j;
}
}
void prepCase2()
{
int j = bpos[0];
for (int i = 0; i <= m; ++ i)
{
if (!shift[i])
shift[i] = j;
if (i == j)
j = bpos[j];
}
}
int main()
{
scanf("%s\n%s", a, b);
m = strlen(a);
n = strlen(b);
int s = 0;
prepCase1();
prepCase2();
while (s <= n - m)
{
int j = m - 1;
while (j >= 0 && a[j] == b[s + j])
-- j;
if (j < 0)
{
if (ans[0] < 1000)
ans[++ ans[0]] = s;
else
++ ans[0];
s += shift[0];
}
else
s += shift[j + 1];
}
printf("%d\n", ans[0]);
for (int i = 1; i <= min(ans[0], 1000); ++ i)
printf("%d ", ans[i]);
return 0;
}