Pagini recente » Cod sursa (job #1893467) | Cod sursa (job #2594595) | Cod sursa (job #49540) | Cod sursa (job #132274) | Cod sursa (job #709976)
Cod sursa(job #709976)
#include <iostream>
#include <fstream>
#include <vector>
#include <locale>
#include <string>
#include <algorithm>
using namespace std;
const int DIM = 1000;
typedef collate<char> cc_t;
string str, pat;
vector<int> matchPos;
inline long long hash(const string& arg, const cc_t& coll)
{
return coll.hash(arg.data(), arg.data() + arg.size());
}
void solve()
{
const cc_t& coll = use_facet<cc_t>(locale());
long long patHash = hash(pat, coll);
int ind = min(pat.size(), str.size());
string tmp = str.substr(0, ind);
for (; ind <= str.size() && matchPos.size() < DIM; ++ind) {
//cerr << tmp << endl;
if (hash(tmp, coll) == patHash) matchPos.push_back(ind - pat.size());
tmp.erase(0, 1);
tmp.push_back(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] << ' ';
fout << endl;
fin.close();
fout.close();
return 0;
}