Mai intai trebuie sa te autentifici.
Cod sursa(job #486571)
Utilizator | Data | 21 septembrie 2010 23:34:24 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.93 kb |
#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)
{
while (q && a[q + 1] != b[i]) q = prefix[q];
if (a[q + 1] == b[i]) ++q;
if (q == sa)
{
q = prefix[q];
if (n < 1000) pos[++n] = i - sa;
else ++n;
}
}
printf("%d \n", n);
for (int i = 1; i <= std::min(n, 1000); ++i)
printf("%d ", pos[i]);
}