Pagini recente » Cod sursa (job #2625727) | Cod sursa (job #2359707) | Cod sursa (job #2571547) | Cod sursa (job #1338659) | Cod sursa (job #443136)
Cod sursa(job #443136)
#include <cstdio>
#include <cstring>
using namespace std;
FILE* fin=fopen("strmatch.in","r");
FILE* fout=fopen("strmatch.out","w");
#define MAX 2000005
#define MAXM 1000
#define SIGMA 128
#define MOD1 100007
#define MOD2 100021
typedef unsigned long long int64;
char a[MAX],b[MAX];
int n,m,match[MAX],nm=0;
bool rabinKarp(){
if(m>n){
return 0;
}else{
unsigned p1=0,p2=0,t1=0,t2=0,h1=1,h2=1;
for(int i=0;i<m;i++){
p1=(SIGMA*p1+b[i])%MOD1;
p2=(SIGMA*p2+b[i])%MOD2;
t1=(SIGMA*t1+a[i])%MOD1;
t2=(SIGMA*t2+a[i])%MOD2;
if(i!=0){
h1=(h1*SIGMA)%MOD1;
h2=(h2*SIGMA)%MOD2;
}
}
for(int s=0;s<=n-m;s++){
if(p1==t1&&p2==t2){
match[nm++]=s;
}
if(s<n-m){
t1=((t1-(a[s]*h1)%MOD1+MOD1)*SIGMA+a[s+m])%MOD1;
t2=((t2-(a[s]*h2)%MOD2+MOD2)*SIGMA+a[s+m])%MOD2;
}
}
return 1;
}
}
int main(){
fgets(b,MAX,fin);
fgets(a,MAX,fin);
n=strlen(a)-1,m=strlen(b)-1;
if(rabinKarp()){
fprintf(fout,"%d\n",nm);
nm=(nm>MAXM)?MAXM:nm;
for(int i=0;i<nm;i++){
fprintf(fout,"%d ",match[i]);
}
fputc('\n',fout);
}else{
fprintf(fout,"0\n");
}
fclose(fin);
fclose(fout);
return 0;
}