Pagini recente » Cod sursa (job #3312091) | Cod sursa (job #2105060) | Cod sursa (job #2104681) | Cod sursa (job #3312102) | Cod sursa (job #2105040)
// Rabin Karp
//#include <iostream>
//#include <conio.h>
#define X 97
#define MOD1 666013
#define MOD2 777013
#define DIM 2000010
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int hashA1 = 0;
int hashA2 = 0;
int hashB1 = 0;
int hashB2 = 0;
int power1 = 1;
int power2 = 1;
char a[DIM], b[DIM];
bool match[DIM];
int cnt = 0;
int lengthA, lengthB;
void Read()
{
ifstream fin("strmatch.in");
fin >> a >> b;
fin.close();
}
void Solve()
{
lengthA = (int)strlen(a);
lengthB = (int)strlen(b);
if (lengthA > lengthB)
return;
for (int i = 0;i < lengthA;++i)
{
hashA1 = (1LL * hashA1 * X + (int)a[i] * X) % MOD1;
hashA2 = (1LL * hashA2 * X + (int)a[i] * X) % MOD2;
power1 = 1LL * power1 * X % MOD1;
power2 = 1LL * power2 * X % MOD2;
}
for (int i = 0;i < lengthA;++i)
{
hashB1 = (1LL * hashB1 * X + (int)b[i] * X) % MOD1;
hashB2 = (1LL * hashB2 * X + (int)b[i] * X) % MOD2;
}
if (hashA1 == hashB1 && hashA2 == hashB2)
{
match[0] = true;
++cnt;
}
for (int i = lengthA;i < lengthB;++i)
{
hashB1 = (1LL * hashB1 - (int)b[i - lengthA] * power1) % MOD1;
hashB2 = (1LL * hashB2 - (int)b[i - lengthA] * power2) % MOD2;
while (hashB1 < 0)
hashB1 += MOD1;
while (hashB2 < 0)
hashB2 += MOD2;
hashB1 = (1LL * hashB1 + (int)b[i]) * X % MOD1;
hashB2 = (1LL * hashB2 + (int)b[i]) * X % MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2)
{
match[i - lengthA + 1] = true;
++cnt;
}
}
}
void Write()
{
ofstream fout("strmatch.out");
int dim = min(1000, cnt);
fout << cnt << "\n";
cnt = 0;
for (int i = 0;i < lengthB && cnt <= 1000;++i)
if (match[i])
{
fout << i << " ";
++cnt;
}
fout.close();
}
int main()
{
Read();
Solve();
Write();
//_getch();
return 0;
}