Pagini recente » Cod sursa (job #2986573) | Cod sursa (job #2848582) | Cod sursa (job #2799906) | Cod sursa (job #2975399) | Cod sursa (job #2424485)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
string const inFile = "strmatch.in";
string const outFile = "strmatch.out";
ifstream Read(inFile);
ofstream Write(outFile);
void SubstringMatching(
string const &_string,
string const &_substring,
vector<unsigned> &pos,
unsigned &_count
) {
if (_substring.size() > _string.size()) {
return;
}
typedef unsigned long long ULL;
ULL prime = 173;
ULL modulo1 = 11654387;
ULL modulo2 = 51054347;
ULL primePow1 = 1;
ULL primePow2 = 1;
ULL stringHash1 = 0;
ULL stringHash2 = 0;
ULL substringHash1 = 0;
ULL substringHash2 = 0;
unsigned i;
for (i = 0; i < _substring.size(); ++i) {
substringHash1 = (substringHash1 * prime + _substring[i]) % modulo1;
substringHash2 = (substringHash2 * prime + _substring[i]) % modulo2;
stringHash1 = (stringHash1 * prime + _string[i]) % modulo1;
stringHash2 = (stringHash2 * prime + _string[i]) % modulo2;
if (i > 0) {
primePow1 = (primePow1 * prime) % modulo1;
primePow2 = (primePow2 * prime) % modulo2;
}
}
unsigned limit = _string.size() - _substring.size() + 1;
for (i = 0; i < limit; ++i) {
if (substringHash1 == stringHash1)
if (substringHash2 == stringHash2) {
if (++_count <= 1000) {
pos.push_back(i);
}
}
if (i == limit - 1) {
break;
}
stringHash1 = stringHash1 - (_string[i] * primePow1) % modulo1 + modulo1;
stringHash1 = stringHash1 * prime + _string[i + _substring.size()];
stringHash1 %= modulo1;
stringHash2 = stringHash2 - (_string[i] * primePow2) % modulo2 + modulo2;
stringHash2 = stringHash2 * prime + _string[i + _substring.size()];
stringHash2 %= modulo2;
}
}
int main() {
string _substring;
string _string;
vector<unsigned> pos;
unsigned _count = 0;
Read >> _substring;
Read >> _string;
SubstringMatching(_string, _substring, pos, _count);
Write << _count << '\n';
for (unsigned i = 0; i < pos.size(); ++i) {
Write << pos[i] << ' ';
}
return 0;
}