Pagini recente » Cod sursa (job #2224692) | Cod sursa (job #1109866) | Cod sursa (job #2483949) | Cod sursa (job #365543) | Cod sursa (job #977997)
Cod sursa(job #977997)
#include <cstdio>
#include <cstring>
#define MAXN 2000001
#define MOD1 666013
#define MOD2 10003
using namespace std;
char s[MAXN], sub[MAXN];
int a[MAXN];
int hash1_sub (int m)
{
int h1=0;
for (int i=0; i<m; i++) h1=(h1*101%MOD1+(int)sub[i])%MOD1; return h1;
}
int hash2_sub (int m)
{
int h2=0;
for (int i=0; i<m; i++) h2=(h2*109%MOD2+(int)sub[i])%MOD2; return h2;
}
int hash1_s (int p, int m)
{
int h1=0;
for (int i=p+0; i<p+m; i++) h1=(h1*101%MOD1+(int)s[i])%MOD1; return h1;
}
int hash2_s (int p, int m)
{
int h2=0;
for (int i=p+0; i<p+m; i++) h2=(h2*109%MOD2+(int)s[i])%MOD2; return h2;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(sub); gets(s); int m=strlen(sub); int n=strlen(s); int nr=0; int i;
if (m>n) {printf("0"); return 0;}
int hsub1=hash1_sub(m); int hsub2=hash2_sub(m); int p=1;
int hs1=hash1_s(0,m); int hs2=hash2_s(0,m); int r=1;
if(hs1==hsub1 && hs2==hsub2){nr++; a[nr]=0;}
for (i=1; i<m; i++) {p=(p*101)%MOD1; r=(r*109)%MOD2;}
for (i=m; i<n; i++)
{
hs1=((hs1-(s[i-m]*p)%MOD1+MOD1)*101+s[i])%MOD1;
hs2=((hs2-(s[i-m]*r)%MOD2+MOD2)*109+s[i])%MOD2;
if(hs1==hsub1 && hs2==hsub2){nr++; a[nr]=i-m+1;}
} printf("%d\n",nr);
for (i=1; i<=nr; i++) if (i<=1000) printf("%d ",a[i]);
fclose(stdin);
fclose(stdout);
return 0;
}