Pagini recente » Cod sursa (job #3248387) | Cod sursa (job #1422336) | Cod sursa (job #400329) | Cod sursa (job #1764308) | Cod sursa (job #911438)
Cod sursa(job #911438)
#include <stdio.h>
#include <string.h>
#include <list>
using namespace std;
#define Nmax 2000005
#define Mod1 100007
#define Mod2 100021
char A[Nmax], B[Nmax];
int n, m, sol, nrsol;
list <int> position;
void read(){
scanf("%s %s", A+1, B+1);
n = strlen(A+1);
m = strlen(B+1);
fclose(stdin);
}
void Rabin_Karp(){
unsigned int p1, p2, b, hA1, hA2, hB1, hB2;
b = 63; p1 = p2 = 1;
hA1 = hA2 = hB1 = hB2 = 0;
for(int i = 1; i <= n; ++i){
hA1 = (hA1*b + A[i])%Mod1;
hA2 = (hA2*b + A[i])%Mod2;
hB1 = (hB1*b + B[i])%Mod1;
hB2 = (hB2*b + B[i])%Mod2;
p1 = (p1*b)%Mod1;
p2 = (p2*b)%Mod2;
}
if(hA1 == hB1 && hA2 == hB2){
++sol;
++nrsol;
position.push_back(0);
}
for(int i = 2; i <= m-n+1; ++i){
hB1 = ( hB1*b - (B[i-1]*p1)%Mod1 + Mod1 + B[i+n-1] )%Mod1;
hB2 = ( hB2*b - (B[i-1]*p2)%Mod2 + Mod2 + B[i+n-1] )%Mod2;
if(hA1 == hB1 && hA2 == hB2){
++sol;
if(nrsol < 1000){
++nrsol;
position.push_back(i-1);
}
}
}
}
void write(){
printf("%i\n", sol);
list <int>::iterator it;
for(it = position.begin(); it != position.end(); ++it)
printf("%i ", *it);
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
read();
Rabin_Karp();
write();
return 0;
}