Pagini recente » Cod sursa (job #156424) | Cod sursa (job #3241868) | Cod sursa (job #920097) | Cod sursa (job #651881) | Cod sursa (job #3209379)
#include <bits/stdc++.h>
#define P 123457
#define Q 777013
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
/**
Algoritmi eficienti:
KMP - Knuth Morris Pratt
Z-Algorithm
Rabin-Karp !
ABA
CABBCABABAB
x1 = ABA
x2 = (CAB - C*26^2)*26 + B
x = 92345678 - 90000000
*/
char a[2000002], b[2000002];
int k, n, poz[2000002], m;
/// A-Z : 0..25
/// a..z: 26..51
///0..9 : 52..61
int Cifra(char ch)
{
if ('A'<= ch && ch <= 'Z') return ch - 'A';
if ('a'<= ch && ch <= 'z') return 26 + ch - 'a';
return 52 + ch - '0';
}
int main()
{
int i, p, q, x1, x2, x3, x4;
fin >> a;
k = strlen(a);
fin >> b;
n = strlen(b);
if (k > n)
{
fout << "0\n";
fout.close();
return 0;
}
p = q = 1;
for (i = 1; i < k; i++)
{
p = p * 62 % P;
q = q * 62 % Q;
}
x1 = x3 = 0;
for (i = 0; i < k; i++)
{
x1 = (x1 * 62 + Cifra(a[i])) % P;
x3 = (x3 * 62 + Cifra(a[i])) % Q;
}
x2 = x4 = 0;
for (i = 0; i < k; i++)
{
x2 = (x2 * 62 + Cifra(b[i])) % P;
x4 = (x4 * 62 + Cifra(b[i])) % Q;
}
if (x1 == x2 && x3 == x4)
poz[++m] = 0;
for (i = k; i < n; i++)
{
x2 = (x2 - Cifra(b[i-k]) * p % P + P) % P;
x2 = (x2 * 62 + Cifra(b[i])) % P;
x4 = (x4 - Cifra(b[i-k]) * q % Q + Q) % Q;
x4 = (x4 * 62 + Cifra(b[i])) % Q;
if (x1 == x2 && x3 == x4)
poz[++m] = i-k+1;
}
fout << m << "\n";
for (i = 1; i <= min(1000, m); i++)
fout << poz[i] << " ";
return 0;
}