Pagini recente » Cod sursa (job #151169) | Cod sursa (job #1237033) | Cod sursa (job #1958543) | Cod sursa (job #2318740) | Cod sursa (job #477119)
Cod sursa(job #477119)
#include <cctype>
#include <cstdio>
#include <algorithm>
char a[2000001], b[2000001];
int sa, sb, prefix[2000001];
int pos[1001], n;
void make_prefix()
{
int q = 0;
for (int i = 2; i <= sa; ++i)
{
while (q && a[i] != a[q + 1])
q = prefix[q];
if (a[i] == a[q + 1]) ++q;
prefix[i] = q;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(a);
gets(b);
for (sa = 0; isdigit(a[sa]) || isalpha(a[sa]); ++sa);
for (sb = 0; isdigit(b[sb]) || isalpha(b[sb]); ++sb);
for (int i = sa; i > 0; --i) a[i] = a[i - 1];
for (int i = sb; i > 0; --i) b[i] = b[i - 1];
make_prefix();
int q = 0;
for (int i = 1; i <= sb; ++i)
{
if (a[q + 1] == b[i])
++q;
else
q = prefix[q];
if (q == sa)
{
q = prefix[q];
pos[++n] = i - sa;
}
}
printf("%d \n", n);
for (int i = 1; i <= std::min(n, 1000); ++i)
printf("%d ", pos[i]);
}