Pagini recente » Cod sursa (job #1470722) | Cod sursa (job #3155193) | Cod sursa (job #507211) | Cod sursa (job #2089275) | Cod sursa (job #591027)
Cod sursa(job #591027)
#include <iostream>
#include <vector>
using namespace std;
#define maxN 2000005
#define baza 73
#define MOD1 100007
#define MOD2 100021
#define PB push_back
char A[maxN], B[maxN];
bool match[maxN];
int hashA1, hashA2, hashB1, hashB2;
int baza1 = 1, baza2 = 1;
vector <int> sol;
int main()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
scanf ("%s %s", A, B);
int lengA = strlen (A);
int lengB = strlen (B);
if (lengA > lengB)
{
printf ("0");
return 0;
}
for (int i = 0; i < lengA; ++ i)
{
hashA1 = (hashA1 * baza + A[i]) % MOD1;
hashA2 = (hashA2 * baza + A[i]) % MOD2;
hashB1 = (hashB1 * baza + B[i]) % MOD1;
hashB2 = (hashB2 * baza + B[i]) % MOD2;
if (i)
{
baza1 = (baza * baza1) % MOD1;
baza2 = (baza * baza2) % MOD2;
}
}
if (hashA1 == hashB1 && hashA2 == hashB2) sol.PB (0);
for (int i = lengA; i < lengB; ++ i)
{
hashB1 = ((hashB1 - (B[i - lengA] * baza1) % MOD1 + MOD1) * baza + B[i]) % MOD1;
hashB2 = ((hashB2 - (B[i - lengA] * baza2) % MOD2 + MOD2) * baza + B[i]) % MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2) sol.PB (i - lengA + 1);
}
printf ("%d \n", sol.size());
for (unsigned int i = 0; i < sol.size() && i < 1000; ++ i)
printf ("%d ", sol[i]);
return 0;
}