Pagini recente » Cod sursa (job #1931452) | Cod sursa (job #2448755) | Cod sursa (job #3191089) | Cod sursa (job #2000401) | Cod sursa (job #169875)
Cod sursa(job #169875)
// 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("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;
for (i = 0;i < m; i++){
h1 = (h1 * BS + s1[i]) % MOD;
h2 = (h2 * BS + s2[i]) % MOD;
if (i) br = (br * BS ) % MOD;
}
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;
}