🔤 Procesamiento de Strings

Algoritmos eficientes para búsqueda de patrones, palíndromos, hashing y suffix arrays.

📚 Contenido

2.1 Visión General 2.2 KMP Algorithm 2.3 Z-Function 2.4 Manacher's Algorithm 2.5 Rolling Hash 2.6 Suffix Array & LCP 2.7 Longest Common Substring 📝 Quiz

📊 2.1 Estructuras y Operaciones de Strings

Operaciones Básicas

Acceso por Índice

O(1) random access en arrays

Concatenación

O(n + m) para strings de longitud n y m

Substring

O(k) para substring de longitud k

Comparación

O(min(n,m)) lexicográfica

Comparación de Algoritmos

Operación	Naive	Optimizado
Pattern Matching	O(nm)	O(n+m) KMP, Z
Longest Palindrome	O(n³)	O(n) Manacher
All Substrings	O(n²)	O(n) Suffix Array
LCS (Substring)	O(n²m)	O(n+m) Suffix Array
Substring Comparison	O(k)	O(1) Rolling Hash

                Key Insight: La mayoría de problemas de strings pueden resolverse eficientemente usando algoritmos especializados que explotan la estructura y propiedades de los strings.
            

🔍 2.2 Knuth-Morris-Pratt (KMP)

                Problema: Dado un texto T de longitud n y un patrón P de longitud m, encontrar todas las ocurrencias de P en T en O(n + m) tiempo.
            

Key Insight

Cuando ocurre un mismatch, no necesitamos reiniciar desde el principio. Usamos la failure function (prefix function) para saltar caracteres.

π[i] = longitud del prefijo propio más largo de P[0..i] que también es sufijo de P[0..i]

Visualización: KMP Pattern Matching

Failure Array π:

Configura texto y patrón, luego presiona Iniciar

Implementación

vector<int> computeFailure(const string& P) {
    int m = P.size();
    vector<int> f(m, 0);
    int j = 0;
    for (int i = 1; i < m; ++i) {
        while (j > 0 && P[i] != P[j]) j = f[j-1];
        if (P[i] == P[j]) ++j;
        f[i] = j;
    }
    return f;
}

vector<int> KMP(const string& T, const string& P) {
    int n = T.size(), m = P.size();
    auto f = computeFailure(P);
    vector<int> res;
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j > 0 && T[i] != P[j]) j = f[j-1];
        if (T[i] == P[j]) ++j;
        if (j == m) {
            res.push_back(i - m + 1);
            j = f[j-1];
        }
    }
    return res;
}

def compute_failure(P):
    m = len(P)
    f = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and P[i] != P[j]:
            j = f[j-1]
        if P[i] == P[j]:
            j += 1
        f[i] = j
    return f

def kmp(T, P):
    n, m = len(T), len(P)
    f = compute_failure(P)
    res = []
    j = 0
    for i in range(n):
        while j > 0 and T[i] != P[j]:
            j = f[j-1]
        if T[i] == P[j]:
            j += 1
        if j == m:
            res.append(i - m + 1)
            j = f[j-1]
    return res

Ventajas de KMP

Nunca retrocede en el texto
Tiempo óptimo O(n + m)
Permite matching en streaming/online

⚡ 2.3 Z-Function

                Definición: Para string S[0..n-1], Z[i] = longitud del substring más largo comenzando en i que coincide con un prefijo de S.
            

Visualización: Z-Function

Z Array:

Z[0] = n (longitud total), Z[i] = match con prefijo desde posición i

Implementación

vector<int> zFunction(const string& s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
    }
    z[0] = n;
    return z;
}

def z_function(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(r - i + 1, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    z[0] = n
    return z

Pattern Matching con Z-Function

Para buscar patrón P en texto T: concatenar S = P + "$" + T, calcular Z, buscar Z[i] == m

def z_match(T, P):
    S = P + "$" + T
    Z = z_function(S)
    m = len(P)
    return [i - m - 1 for i in range(m + 1, len(S)) if Z[i] == m]

Aplicaciones

Pattern matching
Detección de periodicidad
Encontrar palíndromos
Construcción de suffix arrays

🪞 2.4 Manacher's Algorithm

                Problema: Encontrar el substring palindrómico más largo en tiempo lineal O(n).
            

Key Insight

Transformar el string insertando separadores (#) entre caracteres para manejar palíndromos pares e impares uniformemente.

s = "aba" → T = "#a#b#a#"

Visualización: Manacher

P Array (radios):

Palíndromo más largo encontrado aparecerá aquí

Algoritmo Core

Mantener centro C y frontera derecha R del palíndromo actual
Para cada posición i: usar espejo mir = 2C - i
Inicializar radio: P[i] = min(R - i, P[mir]) si i < R
Expandir mientras coincidan caracteres
Actualizar C y R si i + P[i] > R

Implementación

string manacher(const string& s) {
    string T = "#";
    for (char c : s) { T += c; T += '#'; }
    int n = T.size();
    vector<int> P(n);
    int C = 0, R = 0, maxLen = 0, centerIdx = 0;
    
    for (int i = 0; i < n; ++i) {
        int mir = 2 * C - i;
        if (i < R) P[i] = min(R - i, P[mir]);
        while (i + P[i] + 1 < n && i - P[i] - 1 >= 0 &&
               T[i + P[i] + 1] == T[i - P[i] - 1]) ++P[i];
        if (i + P[i] > R) { C = i; R = i + P[i]; }
        if (P[i] > maxLen) { maxLen = P[i]; centerIdx = i; }
    }
    int start = (centerIdx - maxLen) / 2;
    return s.substr(start, maxLen);
}

def manacher(s):
    T = '#' + '#'.join(s) + '#'
    n = len(T)
    P = [0] * n
    C, R = 0, 0
    max_len, center_idx = 0, 0
    
    for i in range(n):
        mir = 2 * C - i
        if i < R:
            P[i] = min(R - i, P[mir])
        while (i + P[i] + 1 < n and i - P[i] - 1 >= 0 and
               T[i + P[i] + 1] == T[i - P[i] - 1]):
            P[i] += 1
        if i + P[i] > R:
            C, R = i, i + P[i]
        if P[i] > max_len:
            max_len, center_idx = P[i], i
    
    start = (center_idx - max_len) // 2
    return s[start:start + max_len]

#️⃣ 2.5 Rolling Hash

Polynomial Hash:

H(s) = Σ (s[i] - 'a' + 1) × p^i mod m

Parámetros

Base p: primo pequeño (ej. 31 o 53)
Módulo m: primo grande (ej. 10⁹ + 7)
Update: O(1) al agregar/remover caracteres

Implementación

class RollingHash {
    static const long long MOD = 1000000007;
    static const long long BASE = 31;
    vector<long long> hash, power;
public:
    RollingHash(const string& s) {
        int n = s.size();
        hash.assign(n + 1, 0);
        power.assign(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            hash[i + 1] = (hash[i] * BASE + (s[i] - 'a' + 1)) % MOD;
            power[i + 1] = (power[i] * BASE) % MOD;
        }
    }
    // Get hash of s[l..r] in O(1)
    long long getHash(int l, int r) {
        return (hash[r + 1] - hash[l] * power[r - l + 1] % MOD + MOD) % MOD;
    }
};

class RollingHash:
    def __init__(self, s, base=31, mod=10**9+7):
        self.mod, self.base = mod, base
        n = len(s)
        self.h = [0] * (n + 1)
        self.p = [1] * (n + 1)
        for i, c in enumerate(s):
            self.h[i + 1] = (self.h[i] * base + ord(c) - ord('a') + 1) % mod
            self.p[i + 1] = (self.p[i] * base) % mod
    
    def get_hash(self, l, r):
        return (self.h[r + 1] - self.h[l] * self.p[r - l + 1]) % self.mod

Double Hashing

                ¿Por qué Double Hash?
                Resistencia a colisiones: Dos valores de hash independientes virtualmente eliminan falsos positivos
Competitive Programming: Confiable bajo inputs adversarios

            

Aplicaciones

Comparación de substrings en O(1) después de O(n) preprocesamiento
Pattern Matching: deslizar ventana, comparar con hash del patrón
Palindrome Checking: comparar hash(s[l..r]) con hash del reverso
Longest Common Substring: búsqueda binaria + checks de hash

📚 2.6 Suffix Array & LCP

                Definición: Un suffix array SA de string S es un array de índices tal que los sufijos S[i..] están en orden lexicográfico.
            

Ejemplo: S = "banana"

SA index	Suffix
5	"a"
3	"ana"
1	"anana"
0	"banana"
4	"na"
2	"nana"

SA = [5, 3, 1, 0, 4, 2]

Construcción O(n log n)

vector<int> buildSA(const string& s) {
    int n = s.size(), k = 1;
    vector<int> sa(n), rank(n), tmp(n);
    for (int i = 0; i < n; ++i) { sa[i] = i; rank[i] = s[i]; }
    while (k < n) {
        auto cmp = [&](int a, int b) {
            if (rank[a] != rank[b]) return rank[a] < rank[b];
            int ra = a + k < n ? rank[a + k] : -1;
            int rb = b + k < n ? rank[b + k] : -1;
            return ra < rb;
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; ++i)
            tmp[sa[i]] = tmp[sa[i-1]] + cmp(sa[i-1], sa[i]);
        rank = tmp;
        k <<= 1;
    }
    return sa;
}

def build_sa(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    k = 1
    while k < n:
        def key(i):
            return (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)
        tmp = [0] * n
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i-1]] + (key(sa[i-1]) < key(sa[i]))
        rank = tmp
        k *= 2
    return sa

LCP Array (Kasai's Algorithm)

LCP[i] = longitud del prefijo común más largo de los sufijos en SA[i] y SA[i-1].

vector<int> buildLCP(const string& s, const vector<int>& sa) {
    int n = s.size(), h = 0;
    vector<int> lcp(n), rank(n);
    for (int i = 0; i < n; ++i) rank[sa[i]] = i;
    for (int i = 0; i < n; ++i) {
        if (rank[i] > 0) {
            int j = sa[rank[i] - 1];
            while (i + h < n && j + h < n && s[i + h] == s[j + h]) ++h;
            lcp[rank[i]] = h;
            if (h > 0) --h;
        }
    }
    return lcp;
}

Aplicaciones

Problema	Método
Pattern Matching	Binary search en O(m log n)
Longest Repeated Substring	max sobre LCP array
LCS (dos strings)	SA en S#T + LCP
Distinct Substrings	n(n+1)/2 - Σ LCP[i]

🔗 2.7 Longest Common Substring

                Problema: Dados strings S (longitud n) y T (longitud m), encontrar su substring común más largo.
            

Solución DP

dp[i][j] = dp[i-1][j-1] + 1 si S[i-1] == T[j-1], sino 0

Tiempo O(nm), espacio O(nm) o O(min(n,m)) optimizado.

Visualización: LCS DP

El LCS aparecerá resaltado en la matriz

Implementación

pair<int, string> longestCommonSubstring(const string& S, const string& T) {
    int n = S.size(), m = T.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    int best = 0, end = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (S[i-1] == T[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > best) {
                    best = dp[i][j];
                    end = i;
                }
            }
        }
    }
    return {best, S.substr(end - best, best)};
}

def longest_common_substring(S, T):
    n, m = len(S), len(T)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    best, end = 0, 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if S[i-1] == T[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > best:
                    best, end = dp[i][j], i
    return S[end - best:end]

Solución con Suffix Array

Concatenar S + "#" + T, construir suffix array y LCP. El LCS es el máximo LCP entre sufijos de strings diferentes.

🔤 Procesamiento de Strings

📚 Contenido

📊 2.1 Estructuras y Operaciones de Strings

Operaciones Básicas

Acceso por Índice

Concatenación

Substring

Comparación

Comparación de Algoritmos

🔍 2.2 Knuth-Morris-Pratt (KMP)

Key Insight

Visualización: KMP Pattern Matching

Implementación

Ventajas de KMP

⚡ 2.3 Z-Function

Visualización: Z-Function

Implementación

Pattern Matching con Z-Function

Aplicaciones

🪞 2.4 Manacher's Algorithm

Key Insight

Visualización: Manacher

Algoritmo Core

Implementación

#️⃣ 2.5 Rolling Hash

Parámetros

Implementación

Double Hashing

Aplicaciones

📚 2.6 Suffix Array & LCP

Ejemplo: S = "banana"

Construcción O(n log n)

LCP Array (Kasai's Algorithm)

Aplicaciones

🔗 2.7 Longest Common Substring

Solución DP

Visualización: LCS DP

Implementación

Solución con Suffix Array

📝 Quiz - String Processing