Pagini recente » Cod sursa (job #1653347) | Cod sursa (job #2477405) | Cod sursa (job #2654539) | Cod sursa (job #1614367) | Cod sursa (job #2337314)
#include <cstdio>
#include <cstring>
using namespace std;
char a[100],b[100];
struct Hash{
int n, m, power, hashh;
void init(char *s, long long len){
power=1;
hashh=0;
for(long long i=len-1; i>=0; i--)
{
hashh=(hashh+(1LL*power*s[i])%m)%m;
if(i)
power=(power*n)%m;
}
}
void roll(char toAdd, char toRemove){
hashh=(((hashh-(1LL*toRemove*power)%m+m)*n)%m+toAdd)%m;
}
};
int main()
{
scanf("%s\n%s",a,b);
int l1=strlen(a),l2=strlen(b);
Hash pHash{31,40099},tHash{31,40099};
Hash oHash{53,319993}, hHash{53,319993};
int nr=0;
int afis[100];
pHash.init(a,l1);
tHash.init(b,l1);
oHash.init(a,l1);
hHash.init(b,l1);
if(pHash.hashh==tHash.hashh && oHash.hashh==hHash.hashh)
afis[++nr]=0;
for(int i=l1; i<l2;i++){
tHash.roll(b[i],b[i-l1]);
hHash.roll(b[i],b[i-l1]);
if(pHash.hashh==tHash.hashh && oHash.hashh==hHash.hashh)
afis[++nr]=i-l1+1;
}
printf("%d\n",nr);
for(int i=1; i<=nr; i++)
printf("%d ",afis[i]);
return 0;
}