Pagini recente » Cod sursa (job #957680) | Cod sursa (job #2413208) | Cod sursa (job #2240032) | Cod sursa (job #488379) | Cod sursa (job #1274786)
#include <cstdio>
#include <cstring>
#define K0 73
#define K1 100007
#define K2 100021
char A[2000005];
char B[2000005];
bool Matches[2000005];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", A, B);
int LenA, LenB;
LenA = strlen(A);
LenB = strlen(B);
if(LenA > LenB)
{
printf("0");
return 0;
}
int HashA1, HashA2;
int Hash1, Hash2;
int P1, P2;
HashA1 = HashA2 = Hash1 = Hash2 = 0;
P1 = P2 = 1;
HashA1 = (HashA1 * K0 + A[0]) % K1;
HashA2 = (HashA2 * K0 + A[0]) % K2;
int i;
for(i = 1 ; i < LenA ; ++i)
{
HashA1 = (HashA1 * K0 + A[i]) % K1;
HashA2 = (HashA2 * K0 + A[i]) % K2;
P1 = (P1 * K0) % K1;
P2 = (P2 * K0) % K2;
}
for(i = 0 ; i < LenA ; ++i)
{
Hash1 = (Hash1 * K0 + B[i]) % K1;
Hash2 = (Hash2 * K0 + B[i]) % K2;
}
int Count = 0;
if(HashA1 == Hash1 && HashA2 == Hash2)
{
Matches[0] = true;
Count++;
}
for(i = LenA ; i < LenB ; ++i)
{
Hash1 = ((Hash1 - (B[i - LenA] * P1) % K1 + K1) * K0 + B[i]) % K1;
Hash2 = ((Hash2 - (B[i - LenA] * P2) % K2 + K2) * K0 + B[i]) % K2;
if(Hash1 == HashA1 && Hash2 == HashA2)
{
Matches[i - LenA + 1] = true;
Count++;
}
}
printf("%d\n", Count);
for(i = 0 ; i <= LenB && Count < 1000 ; ++i)
{
if(Matches[i])
{
Count++;
printf("%d ", i);
}
}
return 0;
}