Significado de los Algoritmos de Alta Precisión

En C++, los tipos de datos convencionales tienen límites inherentes para almacenar números. Por ejemplo, el valor máximo de un int es (2^31)-1 = 2147483647, y en el caso de unsigned int, el rango es de 0 a 4294967295. Incluso con long long, el rango es limiatdo de -9223372036854775808 a 9223372036854775807.

Para situaciones que exceden estos límites, como operaciones con números extremadamente grandes, no podemos utilizar las operaciones aritméticas estándar de C++. Sin embargo, si cambiamos nuestro enfoque y tratamos cada dígito de forma indpeendiente, podemos superar esta restricción. Cada dígito puede almacenarse en un array, lo que nos permite manejar números de cualquier tamaño.

1. Suma de Alta Precisión

El problema típico es la suma de dos números grandes. La solución implica:

• Leer los números como cadenas de texto
• Convertir cada cadena en un array de dígitos
• Realizar la suma dígito por dígito, llevando acarreo cuando sea necesario

// Leer los números como cadenas
string num1, num2;
cin >> num1 >> num2;

// Convertir a arrays de dígitos en orden inverso
vector<int> arr1(num1.size() + 1);
vector<int> arr2(num2.size() + 1);

arr1[0] = num1.size();
arr2[0] = num2.size();

for (int i = 1; i <= arr1[0]; i++) {
    arr1[i] = num1[arr1[0] - i] - '0';
}

for (int i = 1; i <= arr2[0]; i++) {
    arr2[i] = num2[arr2[0] - i] - '0';
}

// Realizar la suma
vector<int> resultado(max(arr1[0], arr2[0]) + 1, 0);
int acarreo = 0;

for (int i = 1; i <= max(arr1[0], arr2[0]); i++) {
    int suma = arr1[i] + arr2[i] + acarreo;
    resultado[i] = suma % 10;
    acarreo = suma / 10;
}

if (acarreo > 0) {
    resultado[max(arr1[0], arr2[0]) + 1] = acarreo;
    resultado[0] = max(arr1[0], arr2[0]) + 1;
} else {
    resultado[0] = max(arr1[0], arr2[0]);
}

// Imprimir el resultado
bool primer_digito = false;
for (int i = resultado[0]; i >= 1; i--) {
    if (!primer_digito && resultado[i] == 0) continue;
    primer_digito = true;
    cout << resultado[i];
}

if (!primer_digito) cout << 0;
</int></int></int>

2. Multiplicación de Alta Precisión

La multiplicación sigue un principio similar a la suma, pero requiere manejar el acarreo de manera diferente. El número de dígitos del resultado es como máximo la suma de los dígitos de los factores menos uno.

// Convertir los números a arrays (similar a la suma)
vector<int> factor1, factor2;
// ... (código de conversión omitido por brevedad)

vector<int> producto(factor1[0] + factor2[0], 0);

for (int i = 1; i <= factor1[0]; i++) {
    for (int j = 1; j <= factor2[0]; j++) {
        producto[i + j - 1] += factor1[i] * factor2[j];
        producto[i + j] += producto[i + j - 1] / 10;
        producto[i + j - 1] %= 10;
    }
}

// Determinar el número real de dígitos del resultado
int pos_final = factor1[0] + factor2[0];
while (pos_final > 1 && producto[pos_final] == 0) {
    pos_final--;
}

producto[0] = pos_final;

// Imprimir el resultado
for (int i = pos_final; i >= 1; i--) {
    cout << producto[i];
}
</int></int>

3. Resta de Alta Precisión

La resta requiere precaución adicional para manejar préstamos y asegurar que siempre estemos restando el número más pequeño del más grande.

// Convertir los números a arrays (similar a la suma)
vector<int> minuendo, sustraendo;
// ... (código de conversión omitido por brevedad)

bool resultado_negativo = false;
if (es_menor(minuendo, sustraendo)) {
    intercambiar(minuendo, sustraendo);
    resultado_negativo = true;
}

vector<int> diferencia(max(minuendo[0], sustraendo[0]) + 1, 0);

for (int i = 1; i <= minuendo[0]; i++) {
    if (minuendo[i] < sustraendo[i]) {
        minuendo[i + 1]--;
        minuendo[i] += 10;
    }
    diferencia[i] = minuendo[i] - sustraendo[i];
}

// Eliminar ceros iniciales
int pos_final = minuendo[0];
while (pos_final > 1 && diferencia[pos_final] == 0) {
    pos_final--;
}

diferencia[0] = pos_final;

// Imprimir el resultado
if (resultado_negativo) cout << "-";
for (int i = pos_final; i >= 1; i--) {
    cout << diferencia[i];
}
</int></int>

4. División de Alta Precisión

La división es la operación más compleja, ya que no podemos simplemente dividir dígito por dígito. En su lugar, podemos tratarla como una serie de restas sucesivas.

string dividir_grandes(string numerador, string denominador) {
    string cociente = "";
    string residuo = "";
    
    for (int i = 0; i < numerador.size(); i++) {
        residuo += numerador[i];
        eliminar_ceros_iniciales(residuo);
        
        int contador = 0;
        while (es_mayor_igual(residuo, denominador)) {
            residuo = restar_grandes(residuo, denominador);
            contador++;
        }
        
        cociente += to_string(contador);
    }
    
    eliminar_ceros_iniciales(cociente);
    if (cociente.empty()) cociente = "0";
    
    return cociente;
}

// Funciones auxiliares
void eliminar_ceros_iniciales(string &num) {
    int pos = 0;
    while (pos < num.size() - 1 && num[pos] == '0') {
        pos++;
    }
    num = num.substr(pos);
}

bool es_mayor_igual(string a, string b) {
    if (a.size() > b.size()) return true;
    if (a.size() < b.size()) return false;
    return a >= b;
}

string restar_grandes(string a, string b) {
    // Implementación de resta de alta precisión (similar a la sección anterior)
    // ...
}

Algoritmo KMP

El algoritmo KMP (Knuth-Morris-Pratt) es un algoritmo de búsqueda de cadenas que busca patrones en un texto de manera eficiente, evitando comparaciones innecesarias mediante el uso de un array de "fallas" (failure function) o función de prefijos.

Implementación del Algoritmo KMP

void construir_funcion_fallo(const string &patron, vector<int> &func_fallo) {
    func_fallo[0] = 0;
    int longitud = 0;
    int i = 1;
    
    while (i < patron.size()) {
        if (patron[i] == patron[longitud]) {
            longitud++;
            func_fallo[i] = longitud;
            i++;
        } else {
            if (longitud != 0) {
                longitud = func_fallo[longitud - 1];
            } else {
                func_fallo[i] = 0;
                i++;
            }
        }
    }
}

void buscar_kmp(const string &texto, const string &patron) {
    vector<int> func_fallo(patron.size());
    construir_funcion_fallo(patron, func_fallo);
    
    int i = 0; // Índice para el texto
    int j = 0; // Índice para el patrón
    
    while (i < texto.size()) {
        if (patron[j] == texto[i]) {
            i++;
            j++;
            
            if (j == patron.size()) {
                cout << "Patrón encontrado en posición: " << i - j + 1 << endl;
                j = func_fallo[j - 1];
            }
        } else {
            if (j != 0) {
                j = func_fallo[j - 1];
            } else {
                i++;
            }
        }
    }
    
    // Imprimir la función de fallo
    cout << "Función de fallo: ";
    for (int valor : func_fallo) {
        cout << valor << " ";
    }
    cout << endl;
}

int main() {
    string texto, patron;
    cout << "Ingrese el texto: ";
    cin >> texto;
    cout << "Ingrese el patrón: ";
    cin >> patron;
    
    buscar_kmp(texto, patron);
    
    return 0;
}
</int></int>