Revizia anterioară Revizia următoare
Z-Algorithm
categorie, autor etc
Date Generale
Determinarea tuturor apariţiilor unui model, într-un text, este o problemă frecvent întâlnită la editoarele de texte. De obicei, textul este un document în editare şi modelul căutat este un anumicat cuvânt, dat de utilizator. Algoritmi eficienţi pentru această problemă pot ajuta la îmbunătăţirea performanţelor editoarelor de texte. Algoritmi de potrivire a şirurilor sunt utilizaţi, de asemenea, în căutarea de modele particulare în secvenţe ADN. Problema poate fi rezolvata in mai multe moduri cu diferite complexitati. Complexitatea vizata este O(|P|+|T|). Exista 3 algoritmi care rezolva problema in aceasta complexitate : Rabin Karp, KMP si Z-Algorithm. Rabin Karp sa comporta in practia mai prost din punct de vedere al timpului de executie, asa ca am sa il scot din start. Mari diferente intre KMP si Z-Algorithm nu exista, functia prefix din KMP respectiv functia zValues din zAlgorithm facand aproximativ acelasi lucru. O diferenta ar fi nivelul de intelegere a celor 2 algoritmi, z-algorithm poate fi inteles mai usor decat KMP. Alegerea algoritmului variaza in functie de problema si de cel care o rezolva. De exemplu problema X se rezolva mult mai usor cu zalgorithm. Un plus pentru zalgorithm ar fi ca poate fi inteles in totalitate.