Inversión de Cadenas

Para invertir una cadena de caracteres en C++, se puede utilizar un enfoque de punteros dobles. El siguiente código muestra una implementación que intercambia los elementos desde los extremos hacia el centro.

void invertirCadena(vector<char>& cadena) {
    int inicio = 0;
    int fin = cadena.size() - 1;
    while (inicio < fin) {
        char temp = cadena[inicio];
        cadena[inicio] = cadena[fin];
        cadena[fin] = temp;
        inicio++;
        fin--;
    }
}</char>

En problemas donde se necesita relenar un arreglo, es común preexpandir el arreglo al tamaño final deseado y luego operar desde el final hacia el principio para evitar sobrescrituras.

Eliminación de Espacios Extra

Se puede usar la técnica de punteros rápido y lento para eliminar espacios adicionales en una cadena y asegurar que solo haya un espacio entre palabras. Aquí se muestra una función que procesa la cadena in-situ.

void limpiarEspacios(string& texto) {
    int escritor = 0;
    for (int lector = 0; lector < texto.size(); ++lector) {
        if (texto[lector] != ' ') {
            if (escritor != 0) {
                texto[escritor++] = ' ';
            }
            while (lector < texto.size() && texto[lector] != ' ') {
                texto[escritor++] = texto[lector++];
            }
        }
    }
    texto.resize(escritor);
}

Algoritmo KMP para Búsqueda de Cadenas

El algoritmo Knuth-Morris-Pratt (KMP) optimiza la búsqueda de un patrón dentro de un texto al reutilizar información de coincidencias previas cuando ocurre un desajuste, evitando reinicios innecesarios. Consiste en dos funciones principales: una para calcular el areglo de fallos (next) y otra para realizar la búsqueda.

La función calcularNext detremina el arreglo que indica el prefijo más largo que también es sufijo para cada posición del patrón.

void calcularNext(int* fallos, const string& patron) {
    int longitud = -1;
    fallos[0] = longitud;
    for (int idx = 1; idx < patron.size(); idx++) {
        while (longitud >= 0 && patron[idx] != patron[longitud + 1]) {
            longitud = fallos[longitud];
        }
        if (patron[idx] == patron[longitud + 1]) {
            longitud++;
        }
        fallos[idx] = longitud;
    }
}

La función buscarSubcadena utiliza el arreglo de fallos para localizar el patrón en el texto de manera eficiente.

int buscarSubcadena(const string& texto, const string& patron) {
    if (patron.empty()) {
        return 0;
    }
    vector<int> fallos(patron.size());
    calcularNext(fallos.data(), patron);
    int coincidencia = -1;
    for (int pos = 0; pos < texto.size(); pos++) {
        while (coincidencia >= 0 && texto[pos] != patron[coincidencia + 1]) {
            coincidencia = fallos[coincidencia];
        }
        if (texto[pos] == patron[coincidencia + 1]) {
            coincidencia++;
        }
        if (coincidencia == patron.size() - 1) {
            return pos - patron.size() + 1;
        }
    }
    return -1;
}</int>