Pagini recente » Cod sursa (job #1498748) | Cod sursa (job #507072) | Cod sursa (job #1947861) | Monitorul de evaluare | Cod sursa (job #2057715)
#define DM 2000005
#include <cstdio>
using namespace std;
FILE * fi = fopen("strmatch.in", "r");
FILE * fo = fopen("strmatch.out", "w");
char s[DM], t[DM], c;
int p[DM], n, m, v[DM], k, cnt;
void getp()
{
k = 0;
for (int i = 2; i <= n; ++i)
{
while (k && s[k+1] != s[i])
k = p[k];
if (s[k+1] == s[i])
++k;
p[i] = k;
}
}
void solve()
{
k = 0;
for (int i = 1; i <= m; ++i)
{
while (k && s[k+1] != t[i])
k = p[k];
if (s[k+1] == t[i])
++k;
if (k == n)
{
++cnt;
if (cnt <= 1000)
v[cnt] = i - n;
k = p[k];
}
}
}
int main()
{
c = getc(fi);
while (c != '\n')
{
s[++n] = c;
c = getc(fi);
}
c = getc(fi);
while (c != EOF)
{
t[++m] = c;
c = getc(fi);
}
getp();
solve();
fprintf(fo, "%d\n", cnt);
(cnt > 1000) ? cnt = 1000:cnt = cnt;
for (int i = 1; i <= cnt; ++i)
fprintf(fo, "%d ", v[i]);
return 0;
}