Pagini recente » Cod sursa (job #1408884) | Cod sursa (job #11611) | Cod sursa (job #52661) | Cod sursa (job #2414410) | Cod sursa (job #170276)
Cod sursa(job #170276)
// 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 73
#define MOD 100003
#define MOD2 100021
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;
************/
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
char s1[MAXN] , s2[MAXN];
scanf("%s%s",s2,s1);
int n = strlen(s1),
m = strlen(s2),
i,j;
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;
}
printf("%d\n" , nr);
if (nr > 1000) nr = 1000;
for (i=0; i<nr; i++)
printf("%d ", sol[i]);
/************
fout << nr << "\n";
if (nr > 1000) nr = 1000;
for (i=0;i<nr;i++)
fout << sol[i] << " ";
fin.close();
fout.close();
************/
return 0;
}