Pagini recente » Cod sursa (job #677166) | Cod sursa (job #402976) | Cod sursa (job #1518153) | Cod sursa (job #2914198) | Cod sursa (job #764470)
Cod sursa(job #764470)
#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 );
if( r.size() <= 1000)
{
out << r.size() << '\n';
for( int i = 0; i < r.size(); i++ )
{
out << r[i] << ' ';
}
}
else
{
out << 1000 << '\n';
for( int i = 0; i < 1000; i++ )
{
out << r[i] << ' ';
}
}
in.close();
out.close();
return 0;
}