Pagini recente » Cod sursa (job #46258) | Cod sursa (job #25375) | Cod sursa (job #14397) | Cod sursa (job #3291458) | Cod sursa (job #169755)
Cod sursa(job #169755)
// 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 // base
#define MOD 100007 // 10 digits, nice one
int sol[MAXN], nr;
int main(void){
ifstream fin("strmatch.in");
ofstream fout("strmacth.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;
for (i = 0;i < m; i++){
h1 = (h1 * BS + s1[i]) % MOD;
h2 = (h2 * BS + s2[i]) % MOD;
br *= BS;
}
br /= BS;
for (i = m-1;i<n;i++){
j = 0;
//fout << h1 << " " << h2 << "\n ";
if (h1 == h2){
for (j=0;j<m;j++){
if (s1[i-j] != s2[m-j-1]) j = m+5;
}
if (j == m){
sol[nr++] = i - m +1;
}
}
h1 = (((h1 - (s1[i - m + 1]*br % MOD) + MOD) % MOD) * BS + s1[i+1]) % MOD;
}
fout << nr << "\n";
for (i=0;i<nr;i++)
fout << sol[i] << " ";
fin.close();
fout.close();
return 0;
}