Pagini recente » Cod sursa (job #2762552) | Cod sursa (job #4187) | Cod sursa (job #2007180) | Cod sursa (job #1326445) | Cod sursa (job #282324)
Cod sursa(job #282324)
#include <cstdio>
#include <cstring>
const int maxl = 2000001;
const int d = 73;
const int mod = 100007;
int n, m;
char a[maxl], b[maxl];
char match[maxl];
int t, p, h, d1, res;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a, maxl, stdin);
fgets(b, maxl, stdin);
a[strlen(a) - 1] = '\0';
b[strlen(b) - 1] = '\0';
n = strlen(a); m = strlen(b);
/*
printf("%s\n", a);
printf("%s\n", b);
*/
d1 = 1;
for (int i = 0; i < n; ++i)
{
p = (p * d + a[i]) % mod;
t = (t * d + b[i]) % mod;
if (i != 0)
d1 = (d1 * d) % mod;
}
for (int i = n - 1; i < m; ++i)
{
if (p == t)
{
int ok = 1;
for (int j = 0; j < n; ++j)
if (a[j] != b[i - n + j + 1])
{
ok = 0;
break;
}
match[i - n + 1] = ok;
if (ok) ++res;
}
if (i < m - 1) t = ((t - (b[i - n + 1] * d1) % mod + mod) * d + b[i + 1]) % mod;
}
printf("%d\n", res);
for (int i = 0; i < m; ++i)
if (match[i]) printf("%d ", i);
return 0;
}