Pagini recente » Cod sursa (job #820543) | Borderou de evaluare (job #1945483) | Cod sursa (job #3318786) | Cod sursa (job #798439) | Cod sursa (job #820540)
Cod sursa(job #820540)
#include<cstdio>
#include<string.h>
#define mod 666013
#define mod2 100107
using namespace std;
char A[2000001], B[2000001];
int poz[1002];
int main()
{
int s1,s2,s21,s22,n=0,pf,pf2,i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",A,B);
int la,lb;
la=strlen(A);
lb=strlen(B);
s1=0;s2=0;
pf=1;pf2=1;
s21=0;s22=0;
for(i=0;i<la;i++)
{
s1=( s1*73 + (A[i]) )%mod;
s2=( s2*73 + (A[i]) )%mod2;
s21=( s21*73 +(B[i]) )%mod;
s22=( s22*73 + (B[i]) )%mod2;
if(i){
pf=(pf*73)%mod;
pf2=(pf2*73)%mod2;
}
}
if(s21==s1&&s22==s2)
{
n++;
poz[n]=0;
}
for(i=la;i<lb;i++)
{
s21=( ( s21 - ( B [ i - la ] ) * pf % mod + mod ) * 73 + (B[i]) ) % mod;
s22=( ( s22 - ( B [ i - la ] ) * pf2 % mod2 + mod2 ) * 73 + (B[i]) ) % mod2;
if( s21==s1 && s22==s2 )
if(n<1000) poz[++n]=i-la+1;
else n++;
}
printf("%d\n",n);
for(i=1;i<=n&&i<=1000;i++)
printf("%d ",poz[i]);
return 0;
}