Pagini recente » Cod sursa (job #1529020) | Cod sursa (job #2140645) | Cod sursa (job #900990) | Cod sursa (job #1061430) | Cod sursa (job #401189)
Cod sursa(job #401189)
#include<stdio.h>
#include<string.h>
#define P 73
#define MOD1 100007
#define MOD2 100021
#define Nmax 2000010
using namespace std;
int P1,P2,HA1,HA2,HB1,HB2,i,A,B,sol,poz[1010];
char a[Nmax],b[Nmax];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",b+1);
scanf("%s",a+1);
A=strlen(a+1);
B=strlen(b+1);
P1=P2=1;
if(B>A) {printf("0"); return 0;}
for(i=1;i<=B;i++)
{
HB1 = ( HB1 * P + b[i] ) % MOD1;
HB2 = ( HB2 * P + b[i] ) % MOD2;
if(i>1)
{
P1 = ( P1 * P ) % MOD1;
P2 = ( P2 * P ) % MOD2;
}
}
for(i=1;i<=B;i++)
{
HA1 = ( HA1 * P + a[i] ) % MOD1;
HA2 = ( HA2 * P + a[i] ) % MOD2;
}
if(HA1==HB1 && HA2==HB2) sol++;
for(; i<=A; i++)
{
HA1 =( ( HA1 - ( a[i-B] * P1 ) % MOD1 + MOD1 ) * P + a[i] ) % MOD1;
HA2 =( ( HA2 - ( a[i-B] * P2 ) % MOD2 + MOD2 ) * P + a[i] ) % MOD2;
if(HA1==HB1 && HA2==HB2)
{
sol++;
if(sol<=1000)
poz[sol]=i-B;
}
}
printf("%d\n",sol);
if(sol>1000) sol=1000;
for(i=1;i<=sol;i++)
printf("%d ",poz[i]);
return 0;
}