Pagini recente » Cod sursa (job #1725896) | Cod sursa (job #2788502) | Cod sursa (job #1409704) | Cod sursa (job #2877651) | Cod sursa (job #2749766)
#include <bits/stdc++.h>
#define P 9987671
#define Q 9981121
using namespace std;
/**
P = 34512773, 123457, 777013
De evitat:
2000000000000000000 :
30000000000000000000000 : 100 = rest 0
Hash:
- tabele de hash (tabele de dispersie)
- cod hash
0-9 : 0..9
a-z : 10..35
A-Z : 36..61
-------
62 de caractere
210
ABA = (A*62+B)*62 + A
ABA = A*62^2 + B * 62^1 + A*62^0 = H = 36*62*62+37*62+36 : P
CABBCABABAB
h1 = CAB
h1 = ((h1 - C * 62^2 + P)*62 + B) % P
72345
h1 = ((723 - 7*100) * 10 + 4) % P
543210
234102 (baza b=5) = 2*b^5+3*b^4+...
*/
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000002];
char b[2000002];
int n;
int cod[256];
int poz[1005], m;
int main()
{
int j, i, h,H, h1,h2, PW = 1, pw = 1, nrPotriviri = 0;
j = 0;
for (i = '0'; i <= '9'; i++)
cod[i] = j++;
for (i = 'a'; i <= 'z'; i++)
cod[i] = j++;
for (i = 'A'; i <= 'Z'; i++)
cod[i] = j++;
fin >> a >> b;
/// construim pe h
h = H = 0;
for (n = 0; a[n] != 0; n++)
{
h = (h * 62 + cod[a[n]]) % P;
H = (H * 62 + cod[a[n]]) % Q;
}
for (i = 1; i < n; i++)
{
pw = pw * 62 % P;
PW = PW * 62 % Q;
}
/// parcurg fiecare secventa de lungime n din b
/// formez primul cod h1 cu primele n car. din b
h1 = h2 = 0;
for (i = 0; i < n; i++)
{
h1 = (h1 * 62 + cod[b[i]]) % P;
h2 = (h2 * 62 + cod[b[i]]) % Q;
}
if (h == h1 && H == h2)
{
nrPotriviri++;
poz[++m] = 0;
}
for (i = n; b[i] != 0; i++)
{
h1 = ((h1 - cod[b[i-n]] * pw % P + P) * 62 + cod[b[i]]) % P;
h2 = ((h2 - cod[b[i-n]] * PW % Q + Q) * 62 + cod[b[i]]) % Q;
if (h == h1 && H == h2)
{
nrPotriviri++;
if (m < 1000) poz[++m] = i - n + 1;
}
}
fout << nrPotriviri << "\n";
for (i = 1; i <= m; i++)
fout << poz[i] << " ";
fout.close();
return 0;
}