Pagini recente » Cod sursa (job #2684405) | Cod sursa (job #697698) | Cod sursa (job #1777093) | Cod sursa (job #1387154) | Cod sursa (job #798713)
Cod sursa(job #798713)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
vector<int> result;
unsigned long computeHash(string str)
{
unsigned long hash = 5381;
int c;
for(int i = 0; i < str.size(); i++)
hash = ((hash << 5) + hash) + (int)str[i];
return hash;
}
void RabinKarp(string a, string b)
{
result = vector<int> ();
int n = a.size();
int m = b.size();
unsigned long hs = computeHash(a);
string sub = b.substr(0, n);
unsigned long hsub = computeHash(sub);
for(int i = 1; i < m - n + 1; i++)
{
if(hs == hsub && a == sub)
{
result.push_back(i - 1);
}
sub = b.substr(i, n);
hsub = computeHash(sub);
}
}
int main()
{
ifstream in ("strmatch.in");
ofstream out("strmatch.out");
string a, b;
in >> a >> b;
RabinKarp(a, b);
if(result.size() > 1000)
{
out << 1000 << '\n';
}
else
{
out << result.size() << '\n';
}
for(int i = 0; i < result.size(); i++)
{
if(i == 1000)
break;
out << result[i] << ' ';
}
in.close();
out.close();
}