Pagini recente » Cod sursa (job #2492458) | Cod sursa (job #133785) | Cod sursa (job #392685) | Cod sursa (job #1927414) | Cod sursa (job #2104680)
// Rabin Karp
//#include <iostream>
//#include <conio.h>
#define X 97
#define Y 113
#define MOD1 666013
#define MOD2 777013
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string a, b;
vector <int> v;
int hashA1 = 0;
int hashA2 = 0;
int hashB1 = 0;
int hashB2 = 0;
int power1 = 1;
int power2 = 1;
void Read()
{
ifstream fin("strmatch.in");
fin >> a >> b;
fin.close();
}
void Repair1(int &x)
{
while (x < 0)
x += MOD1;
}
void Repair2(int &x)
{
while (x < 0)
x += MOD2;
}
void Solve()
{
int lengthA = (int)a.length();
int lengthB = (int)b.length();
if (lengthA > lengthB)
return;
for (int i = 0;i < lengthA;++i)
{
hashA1 = (1LL * hashA1 * X % MOD1 + (int)a[i] * X) % MOD1;
hashA2 = (1LL * hashA2 * Y % MOD2 + (int)a[i] * Y) % MOD2;
}
for (int i = 0;i < lengthA;++i)
{
hashB1 = (1LL * hashB1 * X % MOD1 + (int)b[i] * X) % MOD1;
hashB2 = (1LL * hashB2 * Y % MOD2 + (int)b[i] * Y) % MOD2;
}
if (hashA1 == hashB1 && hashA2 == hashB2)
v.push_back(0);
for (int i = 1;i <= lengthA;++i)
{
power1 = 1LL * power1 * X % MOD1;
power2 = 1LL * power2 * Y % MOD2;
}
for (int i = lengthA;i < lengthB;++i)
{
hashB1 = (1LL * hashB1 - (int)b[i - lengthA] * power1 % MOD1) % MOD1;
hashB2 = (1LL * hashB2 - (int)b[i - lengthA] * power2 % MOD2) % MOD2;
Repair1(hashB1);
Repair2(hashB2);
hashB1 = (1LL * hashB1 + (int)b[i]) * X % MOD1;
hashB2 = (1LL * hashB2 + (int)b[i]) * Y % MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2)
v.push_back(i - lengthA + 1);
}
}
void Write()
{
ofstream fout("strmatch.out");
int dim = min(1000, (int)v.size());
fout << (int)v.size() << "\n";
for (int i = 0;i < dim;++i)
fout << v[i] << " ";
fout.close();
}
int main()
{
Read();
Solve();
Write();
//_getch();
return 0;
}