Pagini recente » Cod sursa (job #2008910) | Cod sursa (job #1059870) | Cod sursa (job #1869302) | Cod sursa (job #767397) | Cod sursa (job #977951)
Cod sursa(job #977951)
#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;
}
}
int hash2_sub (int m)
{
int h1=0;
for (int i=0; i<m; i++)
{
h1=(h1*101%MOD2+(int)sub[i])%MOD2;
}
}
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;
}
}
int hash2_s (int p, int m)
{
int h1=0;
for (int i=p+0; i<p+m; i++)
{
h1=(h1*101%MOD2+(int)s[i])%MOD2;
}
}
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 hs1=hash1_s(0,m); int hs2=hash2_s(0,m);
for (i=0; i<n-m+1; i++)
{
if (hs1==hsub1 && hs2==hsub2)
{
if (!strncmp(s+i,sub,m)) {nr++; a[nr]=i;}
hs1=hash1_s(i,m); hs2=hash2_s(i,m);
}
} printf("%d\n",nr);
for (i=1; i<=nr; i++) printf("%d ",a[i]);
fclose(stdin);
fclose(stdout);
return 0;
}