Pagini recente » Cod sursa (job #259241) | Cod sursa (job #2831783) | Cod sursa (job #3304142) | Cod sursa (job #3325530) | Cod sursa (job #350048)
Cod sursa(job #350048)
#include <cstdio>
#include <cstring>
#define millions 2000005
#define thousand 1005
#define cif 73
char P[millions], T[millions];
int L[millions], D[thousand];
int HP0, HS0, MOD0, PU0;
int HP1, HS1, MOD1, PU1;
int n, m;
// functia care marcheaza corect un deplasament
void found(int d)
{
// numarul de deplasamente corecte creste cu o unitate
D[0] = D[0] + 1;
// daca este printre primele 1000 de deplasamente
if (D[0] <= 1000)
{
// retin deplasamentul in vectorul de deplasamente
D[D[0]] = d;
}
}
// functia de citire a datelor de intrare
void read()
{
// declar si deschid deschid fisierul de intrare
freopen("strmatch.in", "r", stdin);
// primul caracter va fi spatiu pentru a se indexa sirurile de la 1
P[0] = T[0] = ' ';
// citesc sirurile
scanf("%s %s", &P[1], &T[1]);
}
// functia algoritmului naiv
void naive(char P[], char T[])
{
int d, p;
// pentru fiecare deplasament posibil
for (d = 0; d <= n - m; d = d + 1)
{
// pentru fiecare element din model
for (p = 1; p <= m; p = p + 1)
{
// daca suprapunerea nu este perfecta
if (T[d + p] != P[p])
{
// intrerup cautarea
break;
}
}
// daca s-au potrivit m caractere
if (p == m + 1)
{
// am gasit o potrivire
found(d);
}
}
}
// functia algoritmului Rabin Karp
void rabin_karp(char P[], char T[])
{
// daca lungimea modelului depaseste lungimea textului
if (m > n)
{
// nu am de ce sa calculez nimic
return;
}
int p, d;
// valorile retinute in MOD trebuie sa fie numere prime
MOD0 = 666013;
MOD1 = 100007;
// calculez functiile HP1, HP2 ale modelului
PU0 = PU1 = 1;
// pentru fiecare element din model
for (p = 1; p <= m; p = p + 1)
{
// actualizez functia HPk
HP0 = (HP0 * cif + P[p]) % MOD0;
HP1 = (HP1 * cif + P[p]) % MOD1;
// vreau sa calculez CF la puterea m - 1
if (p < m)
{
// actualizez CF la puterea m - 1
PU0 = PU0 * cif % MOD0;
PU1 = PU1 * cif % MOD1;
}
}
// calculez functiile HS1, HS2 ale primei subsecvente a textului
for (p = 1; p <= m; p = p + 1)
{
// actualizez functia HSk
HS0 = (HS0 * cif + T[p]) % MOD0;
HS1 = (HS1 * cif + T[p]) % MOD1;
}
// pentru fiecare deplasament posibil in text
for (d = 0; d <= n - m; d = d + 1)
{
// daca HS0 este egala cu HP0 si HS1 este egala cu HP1
if (HS0 == HP0 && HS1 == HP1)
{
// consider (!) ca am gasit o potrivire
found(d);
}
// daca mai exista subsecventa de lungime m de la deplasamentul urmator
if (d < n - m)
{
// scot primul element din subsecventa curenta si adaug elementul de dupa ultimul din subsecventa curenta
HS0 = ((HS0 + MOD0 - PU0 * T[d + 1] % MOD0) * cif + T[d + m + 1]) % MOD0;
HS1 = ((HS1 + MOD1 - PU1 * T[d + 1] % MOD1) * cif + T[d + m + 1]) % MOD1;
}
}
}
// functia prefix, necesara algoritmului Knuth Morris Pratt
void prefix(char P[])
{
int p, k;
// prefixul-sufix strict maximal al prefixului de lungime 1 este 0
L[1] = 0;
// pentru fiecare prefix al modelului
for (p = 2; p <= m; p = p + 1)
{
// incerc extinderea prefixului-sufix strict maximal al prefixului parcurs inainte
k = L[p - 1];
// cat timp nu are loc o potrivire
while (k > 0 && P[k + 1] != P[p])
{
// micsorez prefixul-sufix strict maximal la prefixul-sufix strict maximal propriu
k = L[k];
}
// daca are loc o potrivire
if (P[k + 1] == P[p])
{
// maresc prefixul-sufix strict maximal cu 1, pentru a include caracterul curent
k = k + 1;
}
// prefixul-sufix strict maximal al prefixului de lungime p este retinut in vectorul L
L[p] = k;
}
}
// functia algoritmului Knuth Morris Pratt
void knuth_morris_pratt(char P[], char T[])
{
int t, k;
// calculez cu functia prefix vectorul L
prefix(P);
// initial, in variabila k se gaseste prefixul-sufix maximal
k = 0;
// pentru fiecare element al textului, in variabila k se gaseste prefixul-sufix maximal
for (t = 1; t <= n; t = t + 1)
{
// cat timp nu are loc o potrivire
while (k > 0 && P[k + 1] != T[t])
{
// micsorez prefixul-sufix maximal la prefixul-sufix strict maximal propriu
k = L[k];
}
// daca are loc o potrivire
if (P[k + 1] == T[t])
{
// maresc prefixul-sufix maximal cu 1, pentru a include caracterul curent
k = k + 1;
}
// daca prefixul-sufix maximal este format din m caractere
if (k == m)
{
// am gasit o potrivire
found(t - m);
// micsorez prefixul-sufix maximal la prefixul-sufix strict maximal propriu
k = L[k];
}
}
}
void solve()
{
// calculez lungimea modelului
m = strlen(P) - 1;
// calculez lungimea textului
n = strlen(T) - 1;
// rezolv problema cu algoritmul naiv, http://infoarena.ro/job_detail/350019, 40p
naive(P, T);
// rezolv problema cu algoritmul Rabin Karp, http://infoarena.ro/job_detail/350047, 100p
//rabin_karp(P, T);
// rezolv problema cu algoritmul Knuth Morris Pratt, http://infoarena.ro/job_detail/350018, 100p
// knuth_morris_pratt(P, T);
}
// functia de scriere a datelor de iesire
void write()
{
int i;
// declar si deschid fisierul de iesire
freopen("strmatch.out", "w", stdout);
// scriu numarul de potriviri
printf("%d\n", D[0]);
// scriu primele 1000 de potriviri
for (i = 1; i <= 1000 && i <= D[0]; ++i)
printf("%d ", D[i]);
}
int main()
{
// citesc datele de intrare
read();
// rezolv problema
solve();
// scriu datele de iesire
write();
return 0;
}