Pagini recente » Cod sursa (job #2278740) | Cod sursa (job #2404787) | Cod sursa (job #2220263) | Cod sursa (job #52150) | Cod sursa (job #169953)
Cod sursa(job #169953)
// Rabin-Karp
// Do not confuse him with Robin Hood
#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <vector.h>
using namespace std;
#define MAXN 2000100
#define BS 103
#define BS2 79
#define MOD 100003
#define MOD2 1000003
int sol[MAXN], nr;
int main(void){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1,s2;
getline(fin,s2);
getline(fin,s1);
int n = s1.size(),
m = s2.size(),
i,j;
s1 = s1 + '!';
int h2 = 0,h1 = 0,br = 1,
hh1 = 0,hh2 = 0, br2 = 1;
for (i = 0;i < m; i++){
h1 = (h1 * BS + s1[i]) % MOD;
h2 = (h2 * BS + s2[i]) % MOD;
if (i) br = (br * BS ) % MOD;
hh1 = (hh1 * BS2 + s1[i]) % MOD2;
hh2 = (hh2 * BS2 + s2[i]) % MOD2;
if (i) br2 = (br2 * BS2) % MOD2;
}
for (i = m-1;i<n;i++){
j = 0;
//fout << h1 << " " << h2 << "\n ";
if (h1 == h2 && hh1 == hh2){
for (j=0;j<m;j++){
if (s1[i-j] != s2[m-j-1]) j = m+5;
}
j = m;
if (j == m){
sol[nr++] = i - m +1;
}
}
h1 = (((h1 - (s1[i - m + 1]*br % MOD) + MOD) % MOD) * BS + s1[i+1]) % MOD;
hh1 = (((hh1 - (s1[i - m + 1]*br2 % MOD2) + MOD2) % MOD2) * BS2 + s1[i+1]) % MOD2;
}
fout << nr << "\n";
for (i=0;i<nr;i++)
fout << sol[i] << " ";
fin.close();
fout.close();
return 0;
}