Pagini recente » Cod sursa (job #2161181) | Cod sursa (job #2519024) | Cod sursa (job #3174419) | Cod sursa (job #1767763) | Cod sursa (job #1871513)
#include <stdio.h>
#include <cstring>
#include <vector>
#define nmax 2000010
#define mod1 666013
#define mod2 666019
#define P 256
using namespace std;
struct hashFunction {
int hash1, hash2;
};
int n, m, nr;
hashFunction p, hashF, currentHash;
char a[nmax], b[nmax];
vector <int> ans;
bool operator==(hashFunction hash1, hashFunction hash2)
{
return (hash1.hash1 == hash2.hash1 && hash1.hash2 == hash2.hash2);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(a + 1); n = strlen(a + 1);
gets(b + 1); m = strlen(b + 1);
hashF.hash1 = 0;
hashF.hash2 = 0;
for (int i = 1; i <= n; i++) {
hashF.hash1 = (1LL * hashF.hash1 * P + a[i]) % mod1;
hashF.hash2 = (1LL * hashF.hash2 * P + a[i]) % mod2;
}
currentHash.hash1 = 0;
currentHash.hash2 = 0;
p.hash1 = 1; p.hash2 = 1;
for (int i = 1; i <= n; i++) {
currentHash.hash1 = (1LL * currentHash.hash1 * P + b[i]) % mod1;
currentHash.hash2 = (1LL * currentHash.hash2 * P + b[i]) % mod2;
if (i > 1) {
p.hash1 = (1LL * p.hash1 * P) % mod1;
p.hash2 = (1LL * p.hash2 * P) % mod2;
}
}
if (currentHash == hashF) { nr = 1; ans.push_back(0); } else
nr = 0;
for (int i = n + 1; i <= m; i++) {
currentHash.hash1 = (currentHash.hash1 - (1LL * b[i - n] * p.hash1) % mod1);
currentHash.hash2 = (currentHash.hash2 - (1LL * b[i - n] * p.hash2) % mod2);
if (currentHash.hash1 < 0) currentHash.hash1 += mod1;
if (currentHash.hash2 < 0) currentHash.hash2 += mod2;
currentHash.hash1 = (1LL * currentHash.hash1 * P + b[i]) % mod1;
currentHash.hash2 = (1LL * currentHash.hash2 * P + b[i]) % mod2;
if (currentHash == hashF) {
nr++;
if (ans.size() < 1000) ans.push_back(i - n);
}
}
printf("%d\n", nr);
for (int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
return 0;
}