Pagini recente » Cod sursa (job #2131177) | Cod sursa (job #2358016) | Cod sursa (job #3161254) | Cod sursa (job #2886454) | Cod sursa (job #443130)
Cod sursa(job #443130)
#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[MAXM],nm=0;
inline int pow(int64 a,int64 p,int64 mod){
int64 x=a,r=1;
while(p){
if(p&1){
r=(r*x)%mod;
}
x=(x*x)%mod,p>>=1;
}
return (int)r;
}
bool rabinKarp(){
if(m>n){
return 0;
}else{
int h1=pow(SIGMA,m-1,MOD1);
int h2=pow(SIGMA,m-1,MOD2);
unsigned p1=0,p2=0,t1=0,t2=0;
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;
}
for(int s=0;s<=n-m;s++){
if(p1==t1&&p2==t2){
nm++;
if(nm<MAXM){
match[nm-1]=s;
}
}
if(s<n-m-1){
t1=((t1-(a[s]*h1)%MOD1+MOD1)*SIGMA+a[s+m])%MOD1;
t2=((t2-(a[s]*h2)%MOD2+MOD2)*SIGMA+a[s+m])%MOD2;
}
}
getchar();
return 1;
}
}
int main(){
fscanf(fin,"%s %s",b,a);
n=strlen(a),m=strlen(b);
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;
}