Pagini recente » Cod sursa (job #1698189) | Cod sursa (job #1890983) | Cod sursa (job #2729077) | Cod sursa (job #20844) | Cod sursa (job #977945)
Cod sursa(job #977945)
#include <cstdio>
#include <cstring>
#define MAXN 2000001
#define MOD 666013
using namespace std;
char s[MAXN], sub[MAXN];
int a[MAXN];
int hash_sub (int m)
{
int h1=0;
for (int i=0; i<m; i++)
{
h1=(h1*101%MOD+(int)sub[i])%MOD;
}
}
int hash_s (int p, int m)
{
int h1=0;
for (int i=p+0; i<p+m; i++)
{
h1=(h1*101%MOD+(int)s[i])%MOD;
}
}
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;
int hsub=hash_sub(m);
int hs=hash_s(0,m);
for (i=0; i<n-m+1; i++)
{
if (hs==hsub)
{
if (!strncmp(s+i,sub,m)) {nr++; a[nr]=i;}
hs=hash_s(i,m);
}
} printf("%d\n",nr);
for (i=1; i<=nr; i++) printf("%d ",a[i]);
fclose(stdin);
fclose(stdout);
return 0;
}