Pagini recente » Cod sursa (job #2152718) | Autentificare | Cod sursa (job #1054900) | Cod sursa (job #1246472) | Cod sursa (job #3170591)
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
//ifstream fin("main.in");
ofstream fout("strmatch.out");
int base = 31, mod = 40099;
int base2 = 53, mod2 = 319993;
long long int power;
char str[2000005], pattern[2000005];
struct Hash {
int base, base2;
int mod, mod2;
long long int value;
Hash() { base = 0, mod = 0, value = 0; }
Hash(int base, int mod) { this->base = base, this->mod = mod, value = 0; }
Hash(int base, int base2, int mod, int mod2) {
this->base = base, this->base2 = base2;
this->mod = mod, this->mod2 = mod2;
}
void roll(char toRemove, char toAdd) {
value = (((value - (long long int)(toRemove * power) % mod) * base) % mod + toAdd) % mod;
}
void init(char *str, int length) {
int p = 1;
for (int i = length - 1; i >= 0; i--, p *= base)
value += (int) (str[i] * p) % mod;
}
bool operator==(const Hash& other) const { return value == other.value; }
};
Hash patternHash(base, base2, mod, mod2), strHash(base, base2, mod, mod2);
int main() {
fin >> pattern >> str;
patternHash.init(pattern, strlen(pattern));
strHash.init(str, strlen(pattern));
int length = strlen(str), pLength = strlen(pattern);
power = pow(base, pLength - 1);
int sol[1005], solutions = 0;
for (int i = pLength - 1; i < length - 1; i++) {
if (strHash == patternHash) {
solutions++;
if (solutions < 1000)
sol[solutions - 1] = i - pLength + 1;
}
strHash.roll(str[i - pLength + 1], str[i + 1]);
}
fout << solutions << "\n";
for (int i = 0; i < solutions && i < 1000; i++)
fout << sol[i] << " ";
}