Pagini recente » Cod sursa (job #820874) | Cod sursa (job #586676) | Cod sursa (job #2648798) | Cod sursa (job #2978244) | Cod sursa (job #2190631)
#include <cstdio>
#include <cstring>
#include <fstream>
using namespace std;
long long cod(char c)
{
if(c>='A' and c<='Z')
return c - 'A';
if(c>='0' and c<='9'){
return c-'0'+'Z'+1;
}
return c-'a'+'Z'+'9'+2;
}
const long long BASE = 29;
const long long MOD = 10000007;
long long powBase[2000005];
long long hashPref[2000005];
char T[2000005];
char P[2000005];
long long cod(char* s)
{
long long answer = 0;
while (s[0] != '\0')
{
answer = (answer * BASE + cod(s[0])) % MOD;
s++; // ca si cand am 'sterge' primul caracter
}
return answer;
}
long long hashh(long long i, long long j)
{
return (hashPref[j] + MOD - hashPref[i - 1] * powBase[j - (i - 1)] % MOD) % MOD;
}
// i j
//abcdefghi
//abcdef
//abc---
int v[2000005];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",P,T);
long long lenT=strlen(T);
long long lenP=strlen(P);
powBase[0]=1;
for(long long i=1;i<=2000005;i++)
powBase[i]=powBase[i-1]*BASE%MOD;
hashPref[0]=(cod(T[0])+MOD)%MOD;
for(long long i=1;i<lenT;i++)
hashPref[i]=(hashPref[i-1]*BASE+cod(T[i]))%MOD;
long long Phash=cod(P);
long long cnt=0;
for(long long i=0;i+lenP<=lenT;i++)
if(Phash==hashh(i,i+lenP-1)){
v[++cnt]=i;
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
printf("%d ",v[i]);
return 0;
}
//6k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25
//6k76k706k70Xo6k6k7066k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU76k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW066k70XoiNso5e95Rt461N26k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N256k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgETvXeyGjU7N25tcg28s1tW06k70XoiNso5e95Rt461N2w5b2E34N4ErScjCUClMzgXeyGjU7N2506k70X