Pagini recente » Cod sursa (job #2858301) | Cod sursa (job #1435579) | Cod sursa (job #2430042) | Cod sursa (job #998780) | Cod sursa (job #2424484)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long ULL;
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;
}
ULL prime = 173;
ULL modulo = 10000019;
ULL primePow = 1;
ULL stringHash = 0;
ULL substringHash = 0;
unsigned i;
for (i = 0; i < _substring.size(); ++i) {
substringHash = (substringHash * prime + _substring[i]) % modulo;
stringHash = (stringHash * prime + _string[i]) % modulo;
if (i > 0) {
primePow = (primePow * prime) % modulo;
}
}
unsigned limit = _string.size() - _substring.size() + 1;
for (i = 0; i < limit; ++i) {
if (substringHash == stringHash) {
if (++_count <= 1000) {
pos.push_back(i);
}
}
if (i == limit - 1) {
break;
}
stringHash = stringHash - (_string[i] * primePow) % modulo + modulo;
stringHash = stringHash * prime + _string[i + _substring.size()];
stringHash %= modulo;
}
}
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;
}