Cómo encontrar la solución ascendente a este problema

Answer 1

Implementación de abajo hacia arriba
Si quiere decir un algoritmo iterativo de abajo hacia arriba, entonces mi solución coincide con su solicitud (le agradezco si puede aclararlo).
La característica principal de este código es que se utilizó una pila explícita, en lugar de la pila implícita que se usa en funciones recursivas.

#include
#include
#include
#include
#include
usando el espacio de nombres estándar;

// Algunas definiciones de ayudantes
#define pii pair
#define psi pair
#define F primero
#definir S segundo

int findPattern (const string & s, const string & p) {
int n = s.size ();
int m = p.size ();

//Apilar
pila St;
St.push (psi (“”, pii (n – 1, m – 1)));

while (St.empty () == false) {
psi e = St.top ();
St.pop ();

pii c = eS;
// Obtener las cordenadas de “punto”
int i = cF;
int j = cS;
psi ne1, ne2;

if (j <0) {// imprime una solución factible
cout << eF << endl;
Hacer continuación;
} más si (i <0) {
Hacer continuación;
}

if (s [i] == p [j]) {
// Encontramos una coincidencia: empuje el “punto” (i – 1, j – 1)
ne1.F = ((char) toupper (s [i])) + eF;
ne1.S = pii (i – 1, j – 1);
St.push (ne1);
}
// Siempre agregue el “punto” (i – 1, j)
ne2.F = s [i] + eF;
ne2.S = pii (i – 1, j);
St.push (ne2);
}

devuelve 0;
}

int main () {
cadena s, p;
cin >> s >> p;
findPattern (s, p);
}

Antecedentes adicionales

Este problema tiene un tiempo de complejidad no polinomial. Para entender esto, piense en el siguiente análisis del peor de los casos:
cadena: aaa… .aa (talla n)
patrón: aaa… .aa (talla m)
Donde [matemáticas] m \ ge n [/ matemáticas].

El número de soluciones es [matemática] {N} \ elegir {k} [/ matemática] que es igual a [matemática] \ frac {n!} {{M!} \ Times (n – m)!} [/ Matemática ] Por lo tanto, no es posible diseñar un algoritmo para resolver este problema con una complejidad temporal mejor que [math] O (n!) [/ ​​Math].

PD: este problema es bastante clásico. En realidad, me pidieron que resolviera una ligera variación de este problema en una entrevista de codificación hace unos meses.

Answer 2

Creo que hay cierta confusión entre lo que dices que estás tratando de lograr y lo que parece que estás tratando de lograr. Su declaración de apertura (redactada de nuevo para asegurarse de que entiendo) es que desea encontrar todas las ocurrencias de la subcadena (B) dentro de la cadena (A). Con el ejemplo de fizzbuzz y fizz proporcionado, esta respuesta es (1) en el desplazamiento (0).

Esto es diferente de lo que veo en su salida. El resultado parece mostrar que está buscando permutaciones de cadena (A) variando el caso. Quizás preguntando cuántas permutaciones de cadena (A) hay donde esta subcadena (B) se puede encontrar usando una búsqueda que no distingue entre mayúsculas y minúsculas.

¿Puedes aclarar?

¡Gracias!
Charlie