Pagini recente » Cod sursa (job #2604122) | Cod sursa (job #2123217) | Cod sursa (job #1458280) | Cod sursa (job #2643770) | Cod sursa (job #579262)
Cod sursa(job #579262)
#include <stdio.h>
#include <fstream>
#include <string.h>
using namespace std;
const int nmax = 2000010;
const int P = 73;
const int Mod1 = 100007;
const int Mod2 = 100021;
char A[nmax], B[nmax];
int match[nmax], NA, NB;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", A, B);
NA = strlen(A);
NB = strlen(B);
if(NA > NB)
{
printf("0\n");
return 0;
}
int hash1, hash2, T1, T2, P1, P2, i, Nr = 0;
P1 = P2 = 1;
hash1 = hash2 = A[0];
T1 = T2 = B[0];
for(i = 1; i < NA; i++)
{
T1 = ((T1 * P) % Mod1 + B[i]) % Mod1;
T2 = ((T2 * P) % Mod2 + B[i]) % Mod2;
hash1 = ((hash1 * P) % Mod1 + A[i]) % Mod1;
hash2 = ((hash2 * P) % Mod2 + A[i]) % Mod2;
P1 = (P1 * P) % Mod1;
P2 = (P2 * P) % Mod2;
}
if(hash1 == T1 && hash2 == T2)
match[0] = 1, Nr++;
for(i = NA; i < NB; i++)
{
T1 = ((T1 - (P1 * B[i - NA]) % Mod1 + Mod1) * P + B[i]) % Mod1;
T2 = ((T2 - (P2 * B[i - NA]) % Mod2 + Mod2) * P + B[i]) % Mod2;
if(T1 == hash1 && T2 == hash2)
match[i - NA + 1] = 1, Nr++;
}
printf("%d\n", Nr);
Nr = 0;
for(i = 0; i < NB && Nr < 1000; i++)
if(match[i])
printf("%d ", i), Nr++;
return 0;
}