Pagini recente » Monitorul de evaluare | Cod sursa (job #125872) | Cod sursa (job #355094) | Cod sursa (job #132399) | Cod sursa (job #350019)
Cod sursa(job #350019)
#include <cstdio>
#define millions 2000001
#define thousand 1001
char P[millions], T[millions];
int L[millions], D[thousand];
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 sirul model
gets(P+1);
// citesc sirul text
gets(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[])
{
}
// 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);
// pentru fiecare element al textului, in variabila k se gaseste prefixul-sufix maximal care se potriveste
for (k = 0, t = 1; t <= n; ++t)
{
// 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
for (m = -1; P[m+1]; ++m);
// calculez lungimea textului
for (n = -1; T[n+1]; ++n);
// rezolv problema cu algoritmul naiv
naive(P, T);
// rezolv problema cu algoritmul Rabin Karp
// rabin_karp(P, T);
// rezolv problema cu algoritmul Knuth Morris Pratt, http://infoarena.ro/job_detail/350018, 100
// 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();
}