Pagini recente » Cod sursa (job #2405122) | Cod sursa (job #2266212) | Cod sursa (job #1310234) | Cod sursa (job #14909) | Cod sursa (job #1340000)
#include <cstring>
#include <cstdio>
#define b1 27
#define b2 29
#define mod1 10007
#define mod2 666013
#define Nmax 2000001
using namespace std;
char x[Nmax], y[Nmax];
int v2, p2, v1, p1, h1, h2, nr, v[Nmax];
void citire(int &n, int &m)
{
scanf("%s%s", &x, &y);
n = strlen(x);
m = strlen(y);
}
void hash(int n)
{
p1 = p2 = 1;
for(int i = 0; i<n; i++)
{
v1 = (v1 * b1 + x[i])% mod1;
v2 = (v2 * b2 + x[i])% mod2;
if(i >= 1)
{
p1 = (p1 * b1) %mod1;
p2 = (p2 * b2) %mod2;
}
}
h1 = h2 = 0;
for(int i = 0; i<n; i++)
{
h1 = (h1 * b1 + y[i]) % mod1;
h2 = (h2 * b2 + y[i]) % mod2;
}
nr = 0;
if(v1 == h1 && v2 == h2)
v[++nr] = 0;
}
void solve(int n, int m)
{
for(int i = n; i<=m; i++)
{
h1 = ((h1- (y[i - n]*p1)% mod1 + mod1) * b1 + y[i])%mod1;
h2 = ((h2 -(y[i - n]*p2)% mod2 + mod2) * b2 + y[i])%mod2;
if(v1 == h1 && v2 == h2)
v[++nr] = i - n + 1;
}
}
void afis()
{
printf("%d\n", nr);
for(int i = 1; i<=nr && i<=1000; i++)
printf("%d ", v[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int n, m, i;
citire(n, m);
hash(n);
solve(n , m);
afis();
return 0;
}