Pagini recente » Cod sursa (job #2607711) | Cod sursa (job #2152075) | Cod sursa (job #768450) | Cod sursa (job #694610) | Cod sursa (job #911415)
Cod sursa(job #911415)
#include <stdio.h>
#include <string.h>
#include <list>
using namespace std;
#define Nmax 2000005
#define MOD 666013
char A[Nmax], B[Nmax];
int n, m, sol, nrsol;
list <int> poz;
void read(){
scanf("%s %s", A+1, B+1);
n = strlen(A+1);
m = strlen(B+1);
fclose(stdin);
}
inline int check(int i){
for(register int j = 0; j < n; ++j)
if(A[j+1] != B[i+j]) return 0;
return 1;
}
void Rabin_Karp(){
int d = 63;
int p = 0, t = 0, h = 1;
for(register int i = 1; i <= n; ++i){
p = (d*p+A[i])%MOD;
t = (d*t+B[i])%MOD;
h = (h*d)%MOD;
}
for(register int i = 1; i <= m-n+1; ++i){
if(p == t)
if(check(i)){
++sol;
if(nrsol < 1000){
++nrsol;
poz.push_back(i-1);
}
}
t = (t*d + B[i+n] - h*B[i]%MOD + MOD) % MOD;
}
}
void write(){
printf("%i\n", sol);
list <int>::iterator it;
for(it = poz.begin(); it != poz.end(); ++it)
printf("%i ", *it);
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
read();
Rabin_Karp();
write();
return 0;
}