Pagini recente » Cod sursa (job #471632) | Cod sursa (job #1759296) | Cod sursa (job #2151623) | Cod sursa (job #2623295) | Cod sursa (job #659140)
Cod sursa(job #659140)
#include <cstdio>
#define m1 127
#define m2 131
#define mod 666013
using namespace std;
int a[100],b[100],i,j,nr,n,sol,h1,h2,v1,v2,p1,p2;
char chr;
int pow(int a,int b)
{
if (b==0) return 1;
if (b%2==0) {
int aux=pow(a,b/2);
return (aux*aux)%mod;
}
else
if (b%2==1) return a*pow(a,b-1)%mod;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
while (1==1)
{
scanf("%c",&chr);
if (chr=='\n') break;
h1=(h1*m1+chr)%mod;
h2=(h2*m2+chr)%mod;
nr++;
}
while (1==1)
{
scanf("%c",&chr);
if (chr=='\n') break;
a[++n]=(int)chr;
}
for (i=1 ;i<=nr;i++)
{
v1=(v1*m1+a[i])%mod;
v2=(v2*m2+a[i])%mod;
}
p1=pow(m1,nr-1);
p2=pow(m2,nr-1);
if (v1==h1 && h2==v2) {sol++;b[sol]=0;}
for (i=nr+1;i<=n;i++)
{
v1=((v1-(a[i-nr]*p1)%mod+mod)%mod*m1+a[i])%mod;
v2=((v2-(a[i-nr]*p2)%mod+mod)%mod*m2+a[i])%mod;
if (v1==h1 && h2==v2) {sol++;b[sol]=i-nr;}
}
printf("%d\n",sol);
if (sol<=1000) for (i=1 ;i<=sol;i++) printf("%d ",b[i]);
else for (i=1;i<=1000;i++) printf("%d",b[i]);
}