String: secuencia de Char.

Búsqueda de un patrón en un texto

• Problema:

  Dada un string t y un string p queremos saber si p se encuentra dentro de t.

• Especificación:

  proc **contiene**(in t, p : seq<Char>, out result : Bool) {
  	Pre{True}
  	Post{result = True <--> (E i : Z) 
  													(0 <= i <= |t| - |p| &L
  													subseq(t, i, i + |p|) = p)
  			}
  }
  

  proc **matches**(in s : seq<Z>, in i : Z, in r: seq<Char>, out result : Bool) {
  	Pre{0 <= i < |s| - |r| && |r| <= |s|}
  	Post{result = True <--> subseq(s, i, i + |r|) = r}
  

• Implementación función auxiliar matches:

  bool **matches**(string &s, int i, string &r) {
  	int k = 0;
  	while (k < r.size() && s[i + k] == r[k]) {
  		k++;
  	}
  	return k == r.size();
  }
  

  $$ T_{\text{matches}}(s, i, r) \in O(|r|) $$

Algoritmo sencillo

bool **contiene**(string &t, string &p) {
	for (int i = 0; i <= t.size() - p.size() && !matches(t, i, p); i++) {
		// skip
	}
	return i <= t.size() - p.size();

$$ T_{\text{contiene}}(t, p) \in O(|p|) \cdot O(|t|) = O(|p| \cdot |t|) $$

Algoritmo KMP

• Idea:

  Tratar de no volver a inspeccionar todo el patrón cada vez que avanzamos en el texto.

  Mantenemos dos índices $l$ (left) y $r$ (right).

• Invariante:

  1. $0 \leq l \leq r \leq |t|$
  2. $\text{subseq}(t, l, r) = \text{subseq}(p, 0, r - l)$
  3. No hay apariciones de $p$ en $\text{subseq}(t, 0, r)$

• Función $\pi$:

  • Bifijo:

    • Una cadena de caracteres $b$ es un bifijo de $s$ si $b \not = s$, $b$ es un prefijo e $s$ y $b$ es un sufijo de $s$.
    • Dada una cadena $s$ su máximo bifijo es único.

  • $\pi(i)$ es la longitud del máximo bifijo de $\text{subseq}(p, 0, i)$.

  • Invariante:

    1. $0 \leq i < j \leq |p|$
    2. $\text{pi}[k] = \pi(k + 1) \qquad 0 \leq k < j$
    3. $i$ es la longitud del máximo bifijo para $\text{subseq}(p, 0, j)$.
    4. $0 \leq \pi(j) \leq i + 1$

  • Implementación:

    vector<int> calcular_pi(string &p) {
    	vector<int> pi(p.size(), 0);
    	int i = 0;
    	for (int j = 1; j < p.size(); j++) {
    		while (i > 0 && p[i] != p[j]) {
    			i = pi[i - 1];
    		}
    		if (p[i == p[j]) {
    			i++;
    		}
    		pi[j] = i;
    	}
    	return pi;
    }
    

  • Función variante:

    • Loop interno:

      $$ f_V = i $$

    • Loop externo:

      $$ f_V = |p| - j $$

  • Complejidad: $O(|p|)$

• Implementación:

  bool **contiene_kmp**(string &t, string &p) {
  	int l = 0; r = 0;
  	vector<int> pi = calcular_pi(p);
  	while(r < t.size() && r - l < p.size()) {
  		if (t[r] == p[r - l]) {
  			r++;
  		}
  		else if (l == r) {
  			r++;
  			l++;
  		} else {
  			l = r - pi[r - l];
  		}
  	}
  	return r - l == p.size();
  }
  

• Función variante:

  $$ f_V = (|t| - l) + (|t| - r) = 2\cdot |t| - l - r $$

• Complejidad:

  $$ O(|t| + |p|) $$