Pagini recente » Cod sursa (job #1155061) | Cod sursa (job #1993480) | Cod sursa (job #1450145) | Cod sursa (job #2274544) | Cod sursa (job #2057712)
#define DM 2000001
#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)
{
v[++cnt] = i - n;
if (cnt == 1000)
return;
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);
for (int i = 1; i <= cnt; ++i)
fprintf(fo, "%d ", v[i]);
return 0;
}