Pagini recente » Cod sursa (job #1739139) | Cod sursa (job #1571321) | Cod sursa (job #1117473) | Cod sursa (job #3251361) | Cod sursa (job #2509731)
#include <fstream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1, s2;
long long int hash_ref1, hash_ref2;
long long int hash_lim1 = 179365926438715;
long long int hash_lim2 = 124674293321839;
long long int hash_lim3 = hash_lim1 * 26;
long long int hash_lim4 = hash_lim2 * 26;
long long int h1, h2;
long long int elim1, elim2;
vector<int> v;
int main()
{
fin >> s1 >> s2;
elim1 = elim2 = 1;
for(int i = 0 ; i < s1.length() ; i++)
{
hash_ref1 = (hash_ref1 * 26 + s1[i] - 'A') % hash_lim1;
hash_ref2 = (hash_ref2 * 26 + s1[i] - 'A') % hash_lim2;
}
for(int i = 0 ; i < s1.length() - 1 ; i++)
{
elim1 = (elim1 * 26) % hash_lim1;
elim2 = (elim2 * 26) % hash_lim2;
h1 = (h1 * 26 + s2[i] - 'A') % hash_lim1;
h2 = (h2 * 26 + s2[i] - 'A') % hash_lim2;
}
for(int i = s1.length() - 1 ; i < s2.length() ; i++)
{
h1 = (h1 * 26 + s2[i] - 'A') % hash_lim1;
h2 = (h2 * 26 + s2[i] - 'A') % hash_lim1;
if( h1 == hash_ref1 && h2 == hash_ref2 )
{
/// avem match
if(v.size() < 1000)
v.push_back( i - s1.length() + 1 );
}
int x = (s2[i - s1.length() + 1] - 'A');
h1 = ( h1 - elim1 * x + hash_lim3 ) % hash_lim1;
h2 = ( h2 - elim2 * x + hash_lim4 ) % hash_lim2;
}
fout << v.size() << '\n';
for(auto it : v)
fout << it << ' ';
}