Pagini recente » Cod sursa (job #1263571) | Cod sursa (job #1345833) | Cod sursa (job #215825) | Cod sursa (job #2262642) | Cod sursa (job #976544)
Cod sursa(job #976544)
# include <cstdio>
# include <cstring>
# include <cmath>
# define MAXN 2000001
# define K 666013
# define Q 10003
using namespace std;
int v1,v2,h1,h2;
int n,i,m,nr;
int P,R,s[MAXN],x;
char a[MAXN],b[MAXN];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(b);
gets(a);
m=strlen(b);
n=strlen(a);
if(m>n)
{
printf("0\n");
return 0;
}
P=R=1;
for(i=0; i<m; ++i)
{
h1=(h1*101%K+b[i])%K;
h2=(h2*109%Q+b[i])%Q;
v1=(v1*101%K+a[i])%K;
v2=(v2*109%Q+a[i])%Q;
if(h1==v1 && h2==v2)
{
nr++;
s[++x]=0;
}
if(i!=0)
{
P=(P*101)%K;
R=(R*109)%Q;
}
}
if(v1==h1 && v2==h2)
{
nr++;
s[++x]=i-m+1;
}
for(i=m; i<n; ++i)
{
v1 = ( (v1 - (a[ i - m]*P)% K + K)*101 + a[i])%K;
v2 = ( (v2 - (a[ i - m]*R)% Q + Q)*109 + a[i])%Q;
if(v1==h1 && v2==h2)
{
nr++;
s[++x]=i-m+1;
}
}
printf("%d\n", nr);
for(i=1; i<=x && i<=1000; ++i) printf("%d ", s[i]);
return 0;
}