Pagini recente » Cod sursa (job #832354) | Cod sursa (job #1778080) | Cod sursa (job #1446333) | Cod sursa (job #488555) | Cod sursa (job #1128141)
#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 rabinKarp(){
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("%d\n", sol);
list <int>::iterator it;
for(it = position.begin(); it != position.end(); ++it)
printf("%d ", *it);
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
read();
rabinKarp();
write();
return 0;
}