Pagini recente » Cod sursa (job #2971249) | Cod sursa (job #1669422) | Cod sursa (job #948467) | Cod sursa (job #670555) | Cod sursa (job #2104679)
// Rabin Karp
//#include <iostream>
//#include <conio.h>
#define X 97
#define MOD 666013
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string a, b;
vector <int> v;
int hashA = 0;
int hashB = 0;
int power = 1;
void Read()
{
ifstream fin("strmatch.in");
fin >> a >> b;
fin.close();
}
void Repair(int &x)
{
while (x < 0)
x += MOD;
}
void Solve()
{
int lengthA = (int)a.length();
int lengthB = (int)b.length();
if (lengthA > lengthB)
return;
for (int i = 0;i < lengthA;++i)
hashA = (1LL * hashA * X % MOD + (int)a[i] * X) % MOD;
for (int i = 0;i < lengthA;++i)
hashB = (1LL * hashB * X % MOD + (int)b[i] * X) % MOD;
if (hashA == hashB)
v.push_back(0);
for (int i = 1;i <= lengthA;++i)
power = 1LL * power * X % MOD;
for (int i = lengthA;i < lengthB;++i)
{
hashB = (1LL * hashB - (int)b[i - lengthA] * power % MOD) % MOD;
Repair(hashB);
hashB = (1LL * hashB + (int)b[i]) * X % MOD;
if (hashA == hashB)
v.push_back(i - lengthA + 1);
}
//59323745 % 666013 == 485888
//620994
//6305
//59.951.044
}
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;
}