Pagini recente » Cod sursa (job #1407576) | Cod sursa (job #2067744) | Cod sursa (job #160003) | Cod sursa (job #1564770) | Cod sursa (job #1054043)
#include <cstdio>
#include <vector>
#include <cstring>
#define Mod1 666013
#define Mod2 10003
#define p 73
using namespace std;
vector <int> h1[Mod1],h2[Mod2];
vector <int> :: iterator it;
char a[2000001], b[2000001];
int na, nb,i;
int hasha1, hasha2, p1, p2;
char match[2000001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
na = strlen(a);
nb = strlen(b);
p1 = p2 = 1;
hasha1 = hasha2 = 0;
for (int i = 0; i < na; i++)
{
hasha1 = (hasha1 * p + a[i]) % Mod1;
hasha2 = (hasha2 * p + a[i]) % Mod2;
if (i != 0)
p1 = (p1 * p) % Mod1,
p2 = (p2 * p) % Mod2;
}
if (na> nb)
{
printf("0\n");
return 0;
}
int hash1 = 0, hash2 = 0;
for (int i = 0; i <na; i++)
hash1 = (hash1 * p + b[i]) % Mod1,
hash2 = (hash2 * p + b[i]) % Mod2;
int Nr = 0;
if (hash1 == hasha1 && hash2 == hasha2)
{ match[0] = 1; Nr++;}
for (int i = na; i < nb; i++)
{
hash1 = ((hash1 - (b[i - na] * p1) % Mod1 + Mod1) * p + b[i]) % Mod1;
hash2 = ((hash2 - (b[i - na] * p2) % Mod2 + Mod2) * p + b[i]) % Mod2;
if (hash1 == hasha1 && hash2 == hasha2)
match[ i - na + 1 ] = 1, Nr++;
}
printf("%d\n", Nr);
Nr = 0;
for (int i = 0; i < nb && Nr < 1000; i++)
if (match[i])
{
Nr++;
printf("%d ", i);
}
return 0;
}