Pagini recente » Cod sursa (job #881951) | Cod sursa (job #2986693) | Cod sursa (job #2314420) | Cod sursa (job #1110648) | Cod sursa (job #1167114)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int LMAX = 2000000+5;
const int MOD1 = 100007;
const int MOD2 = 100009;
const int MOD3 = 666013;
void Read(),Solve(),Print();
int LA,LB,Nr_Potriviri;
char A[LMAX];
char B[LMAX];
int Potriviri[1005];
int B1,B2,B3;
int Hash1_A,Hash2_A,Hash3_A;
int Hash1_B,Hash2_B,Hash3_B;
int main()
{
Read();
Solve();
Print();
return 0;
}
void Read()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",A+1);
scanf("%s",B+1);
}
void Solve()
{
int i;
LA = strlen(A+1);
LB = strlen(B+1);
B1 = B2 = B3 = 1;
for(i = 1; i <= LA; i++)
{
Hash1_A = (Hash1_A * 48 + A[i]-'A'+1)%MOD1;
Hash2_A = (Hash2_A * 48 + A[i]-'A'+1)%MOD2;
Hash3_A = (Hash3_A * 48 + A[i]-'A'+1)%MOD3;
if(i >= 2) B1 = (B1 * 48)%MOD1;
if(i >= 2) B2 = (B2 * 48)%MOD2;
if(i >= 2) B3 = (B3 * 48)%MOD3;
Hash1_B = (Hash1_B * 48 + B[i]-'A'+1)%MOD1;
Hash2_B = (Hash2_B * 48 + B[i]-'A'+1)%MOD2;
Hash3_B = (Hash3_B * 48 + B[i]-'A'+1)%MOD3;
}
if(Hash1_A == Hash1_B && Hash2_A == Hash2_B && Hash3_A == Hash3_B)
{
Nr_Potriviri++;
if(Nr_Potriviri <= 1000) Potriviri[Nr_Potriviri] = i - LA;
}
for(i = LA + 1; i <= LB; i++)
{
Hash1_B = ((Hash1_B - B1 * (B[i-LA]-'A'+1)) * 48 + B[i]-'A'+1)%MOD1;
Hash2_B = ((Hash2_B - B2 * (B[i-LA]-'A'+1)) * 48 + B[i]-'A'+1)%MOD2;
Hash3_B = ((Hash3_B - B3 * (B[i-LA]-'A'+1)) * 48 + B[i]-'A'+1)%MOD3;
if(Hash1_A == Hash1_B && Hash2_A == Hash2_B && Hash3_A == Hash3_B)
{
Nr_Potriviri++;
if(Nr_Potriviri <= 1000) Potriviri[Nr_Potriviri] = i - LA;
}
}
}
void Print()
{
int i;
printf("%d\n",Nr_Potriviri);
for(i = 1; i <= min(1000,Nr_Potriviri); i++)
printf("%d ",Potriviri[i]);
}