Pagini recente » Cod sursa (job #3222420) | Cod sursa (job #567250) | Cod sursa (job #616439) | Cod sursa (job #490161) | Cod sursa (job #2424475)
#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);
inline bool CompareSubstringInString(
string const &_substring,
string const &_string,
unsigned const index
) {
for (unsigned i = 0; i < _substring.size(); ++i) {
if (i == _string.size()) {
return false;
}
if (_string[i + index] != _substring[i]) {
return false;
}
}
return true;
}
inline void SubstringMatching(
string const &_string,
string const &_substring,
vector<unsigned> &pos
) {
if (_substring.size() > _string.size()) {
return;
}
int charCount = 1 << 8;
int prime = 101;
int _hash = 1;
int stringHash = 0;
int substringHash = 0;
unsigned i;
for (i = 1; i < _substring.size(); ++i) {
_hash = (_hash * charCount) % prime;
}
for (i = 0; i < _substring.size(); ++i) {
substringHash = (substringHash * charCount + _substring[i]) % prime;
stringHash = (stringHash * charCount + _string[i]) % prime;
}
unsigned limit = _string.size() - _substring.size() + 1;
for (i = 0; i < limit; ++i) {
if (substringHash == stringHash) {
if (CompareSubstringInString(_substring, _string, i) == true) {
pos.push_back(i);
}
}
if (i == limit - 1) {
break;
}
stringHash = (stringHash - _string[i] * _hash) * charCount;
stringHash = (stringHash + _string[i + _substring.size()]) % prime;
stringHash = (stringHash + prime) % prime;
}
}
int main() {
string _substring;
string _string;
vector<unsigned> pos;
Read >> _substring;
Read >> _string;
SubstringMatching(_string, _substring, pos);
Write << pos.size() << '\n';
for (unsigned i = 0; i < pos.size(); ++i) {
Write << pos[i] << ' ';
}
return 0;
}