Pagini recente » Cod sursa (job #2663851) | Cod sursa (job #1443605) | Cod sursa (job #1046693) | Cod sursa (job #700607) | Cod sursa (job #2520097)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
///Possible BASES
//for all uppercase/lowercase letters strings
//#define BASE 31
//for alphabet uppercase+lowercase letters strings
//#define BASE 73
//for alphanumeric strings
//#define BASE 79
//#define BASE 2333
///Possible MODS (you can just use long long overflow => MOD=2^64)
//#define MOD 10007
//#define MOD 10009
//#define MOD 666013
//#define MOD 666019
//#define MOD 1000000007
//#define MOD 1000000009
#define BASE 113
#define MOD1 10007
#define MOD2 10009
const int NMAX = 2000003;///max size of string
char s[NMAX]; //string to be searched
char w[NMAX]; //word to search
int mch=0; //number of pozes
bool poz[NMAX]; //poz[i]=1 => there is a match at position i
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",w,s); //read strings
int n=strlen(s);
int m=strlen(w);
if(m>n){
printf("0\n");
return 0;
}
int hashw1=0,hashw2=0;
int hashs1=0,hashs2=0;
int p1=1,p2=1;
///make hash for word
for(int i=0;i<m;++i){
hashw1=(hashw1*BASE+w[i])%MOD1;
hashw2=(hashw2*BASE+w[i])%MOD2;
//computing BASE^(m-1) #highest power in hash
if(i){
p1=(p1*BASE)%MOD1;
p2=(p2*BASE)%MOD2;
}
}
//compute hash for initial m characters
for(int i=0;i<m;++i){
hashs1=(hashs1*BASE+s[i])%MOD1;
hashs2=(hashs2*BASE+s[i])%MOD2;
}
//check if there is a poz
if(hashs1==hashw1 && hashs2==hashw2)
++mch,poz[0]=1;
//compute remaining hashes and check if there is a poz
for(int i=m;i<n;++i){
hashs1=((hashs1-(s[i-m]*p1)%MOD1+MOD1)*BASE+s[i])%MOD1;
hashs2=((hashs2-(s[i-m]*p2)%MOD2+MOD2)*BASE+s[i])%MOD2;
//check if there is a poz
if(hashs1==hashw1 && hashs2==hashw2)
++mch,poz[i-m+1]=1;
}
//display
printf("%d\n",mch);
int cnt=0;
for(int i=1;i<n && cnt<1000;++i)
if(poz[i])
printf("%d ",i),cnt++;
return 0;
}