Pagini recente » Cod sursa (job #1545912) | Cod sursa (job #2117568) | Cod sursa (job #1372885) | Cod sursa (job #864095) | Cod sursa (job #710064)
Cod sursa(job #710064)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
class Hash {
/**
* Simple hashing class.
* Works with string objects.
* Optimized update.
*
* Hash(arg) -> make hash
* get() -> get hash
* del() -> erase first char
* add() -> append char
*/
private:
typedef unsigned int hash_type;
static const hash_type MOD = 63013;
static const hash_type BAS = 101; // base
hash_type hash, exp;
queue<char> que;
hash_type power(hash_type exp)
{
hash_type res = 1, tmp = BAS;
while (exp) {
if (exp % 2) res = (res * tmp) % MOD;
tmp = (tmp * tmp) % MOD;
exp /= 2;
}
return res;
}
public:
Hash(string arg="")
{
hash = 0;
exp = arg.size() - 1;
for (int i = 0; i <= exp; ++i) {
que.push(arg[i]);
hash = (hash + arg[i] * power(exp - i)) % MOD;
}
}
hash_type get() const
{
return hash;
}
void del()
{
if (que.empty()) return;
hash -= (que.front() * power(exp)) % MOD;
que.pop();
}
void add(char chr)
{
hash = (hash * BAS + chr) % MOD;
que.push(chr);
}
bool operator==(const Hash& arg) const
{
return get() == arg.get();
}
};
const int DIM = 1000;
string str, pat;
vector<int> matchPos;
void solve()
{
Hash patHash(pat);
int ind = min(pat.size(), str.size());
Hash strHash(str.substr(0, ind));
for (; matchPos.size() < DIM; ++ind) {
if (patHash == strHash) matchPos.push_back(ind - pat.size());
if (ind == str.size()) break;
strHash.del();
strHash.add(str[ind]);
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> pat >> str;
solve();
fout << matchPos.size() << '\n';
for (int i = 0; i < matchPos.size(); ++i) fout << matchPos[i] << ' ';
fin.close();
fout.close();
return 0;
}