Pagini recente » Cod sursa (job #235038) | Cod sursa (job #2037267) | Cod sursa (job #828162) | Cod sursa (job #2861887) | Cod sursa (job #879982)
Cod sursa(job #879982)
#include <stdio.h>
#include<string.h>
using namespace std;
#define mod 131
#define baza 128
char p[2000002],t[2000002];
int h[2000002],n,m,hashp,w=1,poz[1001],nr;
void citire(){
freopen("strmatch.in","r",stdin);
gets(p);
gets(t);
m=strlen(p)-1;
n=strlen(t)-1;
fclose(stdin);
}
void hashing(){
int i,hasht=0;
for(i=0;i<=m;i++){
hashp=(hashp*baza+(int)p[i])%mod;
hasht=(hasht*baza+(int)t[i])%mod;
if(i<m)
w=w*baza;
}
w=w%mod;
h[0]=hasht;
for(i=1;i<=n-m;i++){
h[i]=h[i-1]+baza*mod-(int)t[i-1]*w;
h[i]=(h[i]*baza+(int)t[i+m])%mod;
}
}
int main()
{ citire();
hashing();
freopen("strmatch.out","w",stdout);
for(int i=0;i<=n-m;i++)
if(h[i]==hashp){
nr++;
poz[nr]=i;
}
printf("%d\n",nr);
for(int i=1;i<=nr;i++)
printf("%d ",poz[i]);
fclose(stdout);
return 0;
}