Pagini recente » Cod sursa (job #3277415) | Cod sursa (job #1405155) | Cod sursa (job #1493833) | Cod sursa (job #582103) | Cod sursa (job #1274781)
#include <cstdio>
#include <cstring>
#define K0 73
#define K1 100007
#define K2 100021
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
char *A = new char[2000005];
char *B = new char[2000005];
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;
int *Matches = new int[2000005];
if(HashA1 == Hash1 && HashA2 == Hash2)
Matches[++Count] = 1;
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[++Count] = i - LenA + 1;
}
printf("%d\n", Count);
for(i = 1 ; i <= Count ; ++i)
printf("%d ", Matches[i]);
delete[] A;
delete[] B;
delete[] Matches;
return 0;
}