Pagini recente » Cod sursa (job #72015) | Cod sursa (job #542481) | Cod sursa (job #2855051) | Cod sursa (job #373282) | Cod sursa (job #2795630)
#include <stdio.h>
#include <string.h>
#define LMAX 2000000
#define MOD 666036
#define BASE 256
int v[1000];
char sir[LMAX + 1];
int lsir;
char subs[LMAX + 1];
int lsubs;
int lgput(int a,int n){
int p;
p=1;
while(n>0){
if((n&1)==1)
p=(long long)p*a%MOD;
a=(long long)a*a%MOD;
n>>=1;
}
return p;
}
bool verificare(char sir[],char subs[]){
int i;
i=0;
while(sir[i] && subs[i] && sir[i]==subs[i])
i++;
return subs[i]==0;
}
int hash(char sir[],int l) {
int h,i;
i=h=0;
while(i<l){
h=(h*BASE+sir[i])%MOD;
i++;
}
return h;
}
int cautare(int lsir,int lsubs){
int sirh,subsh,pow,i,nr;
subsh=hash(subs,lsubs);
sirh=hash(sir,lsubs-1);
pow=lgput(BASE,lsubs-1);
i=lsubs;
nr=0;
while(i<=lsir){
sirh=(sirh*BASE+sir[i-1])%MOD;
if(subsh ==sirh && verificare(sir+i-lsubs,subs)){
if(nr<1000)
v[nr]=i-lsubs;
nr++;
}
sirh-=sir[i-lsubs]*pow%MOD;
if(sirh<0)
sirh+=MOD;
i++;
}
return nr;
}
int main(){
int i,nr;
FILE *fin,*fout;
fin=fopen("strmatch.in", "r");
fout=fopen("strmatch.out", "w");
fgets(subs,sizeof(subs),fin);
lsubs=strlen(subs);
if(subs[lsubs-1]=='\n')
subs[--lsubs]=0;
fgets(sir,sizeof(sir),fin);
lsir=strlen(sir);
if(sir[lsir-1]=='\n')
sir[--lsir]=0;
nr=cautare(lsir,lsubs);
fprintf(fout,"%d\n",nr);
if(nr>1000)
nr=1000;
for(i=0;i<nr;i++)
fprintf(fout,"%d ",v[i]);
fclose(fin);
fclose(fout);
return 0;
}