Pagini recente » Istoria paginii runda/ada9/clasament | Cod sursa (job #482040) | Istoria paginii utilizator/mihaia | Istoria paginii utilizator/cristiansandu | Cod sursa (job #764469)
Cod sursa(job #764469)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>
int hash( std::string str )
{
int base = 101;
//int p = str.size() - 1;
int h = 0;
for( int i = 0; i < str.size(); i++ )
{
h += (int)str[i]; //* pow( base, p );
//p--;
}
return h;
}
std::vector<int> rabin_karp( std::string str, std::string sub )
{
std::vector<int> r;
int hsub = hash( sub );
int hstr = hash( str.substr( 0, sub.size() ) );
for( int i = 0; i <= str.size() - sub.size(); i++ )
{
if( hsub == hstr )
{
if( str.substr( i, sub.size() ) == sub )
{
r.push_back( i );
}
}
hstr = hstr - (int)str[i] + (int)str[i + sub.size()];//hash( str.substr( i + 1, sub.size() ) );
}
return r;
}
int main()
{
std::ifstream in ( "strmatch.in" );
std::ofstream out ( "strmatch.out" );
std::string str, sub;
in >> sub >> str;
std::vector<int> r = rabin_karp( str, sub );
out << r.size() << '\n';
for( int i = 0; i < r.size(); i++ )
{
out << r[i] << ' ';
}
in.close();
out.close();
return 0;
}