algorithm - una - funciones de cadenas de caracteres en c++

Divida una cadena en una cadena de palabras válidas usando la Programación Dinámica

Question

Necesito encontrar un algoritmo de programación dinámica para resolver este problema. Lo intenté pero no pude resolverlo. Aquí está el problema:

Te dan una cadena de n caracteres s [1 ... n], que crees que es un documento de texto dañado en el que toda la puntuación se ha desvanecido (para que se parezca a "itwasthebestoftimes ..."). Desea reconstruir el documento utilizando un diccionario, que está disponible en forma de una función booleana dict (*) tal que, para cualquier cadena w, dict (w) tiene valor 1 si w es una palabra válida, y tiene valor 0 de otra manera.

1. Proporcione un algoritmo de programación dinámica que determine si la cadena s [*] se puede reconstituir como una secuencia de palabras válidas. El tiempo de ejecución debe ser como máximo O (n ^ 2), suponiendo que cada llamada a dict toma un tiempo de unidad.
2. En el caso de que la cadena sea válida, haga que su algoritmo genere la secuencia de palabras correspondiente.

Answer 1

Deje que la longitud de su documento compactado sea N.

Sea b (n) un booleano: verdadero si el documento se puede dividir en palabras comenzando desde la posición n en el documento.

b (N) es verdadero (ya que la cadena vacía se puede dividir en 0 palabras). Dado b (N), b (N - 1), ... b (N - k), puede construir b (N - k - 1) considerando todas las palabras que comienzan en el carácter N - k - 1. Si hay cualquier palabra, w, con b (N - k - 1 + len (w)) establecida, luego establezca b (N - k - 1) en verdadero. Si no hay tal palabra, entonces configure b (N - k - 1) en falso.

Eventualmente, calcula b (0) que le dice si el documento completo se puede dividir en palabras.

En pseudo-código:

def try_to_split(doc):
  N = len(doc)
  b = [False] * (N + 1)
  b[N] = True
  for i in range(N - 1, -1, -1):
    for word starting at position i:
      if b[i + len(word)]:
        b[i] = True
        break
  return b

Hay algunos trucos que puede hacer para que la palabra ''comience en la posición i'' sea eficiente, pero se le pide un algoritmo O (N ^ 2), por lo que puede buscar cada cadena que comience en el diccionario.

Para generar las palabras, puede modificar el algoritmo anterior para almacenar las palabras buenas, o simplemente generarlo así:

def generate_words(doc, b, idx=0):
  length = 1
  while true:
    assert b(idx)
    if idx == len(doc): return
    word = doc[idx: idx + length]
    if word in dictionary and b(idx + length):
       output(word)
       idx += length
       length = 1

Aquí b es la matriz booleana generada a partir de la primera parte del algoritmo.

Answer 2

El O(N^2) Dp es claro pero si conoces las palabras del diccionario, creo que puedes usar algunas precomputaciones para hacerlo aún más rápido en O(N) . Aho-Corasick

Answer 3

La cadena s [] se puede dividir potencialmente en más de una forma. El siguiente método encuentra la cantidad máxima de palabras en la que podemos dividir s []. A continuación se muestra el boceto / pseudocódigo del algoritmo

bestScore [i] -> Almacena el número máximo de palabras en las que se pueden dividir los primeros i caracteres (de lo contrario, sería MINUS_INFINITY)

for (i = 1 to n){
     bestScore[i] = MINUS_INFINITY
     for (k = 1 to i-1){
        bestScore[i] = Max(bestSCore[i], bestScore[i-k]+ f(i,k))
     }
 }

Donde f (i, k) se define como:

f(i,k) = 1 : if s[i-k+1 to i] is in dictionary
       = MINUS_INFINITY : otherwise

bestScore [n] almacenaría la cantidad máxima de palabras en las que s [] se puede dividir (si el valor es MINUS_INFINIY, s [] no se puede dividir)

Claramente, el tiempo de ejecución es O (n ^ 2)

Como esto parece un ejercicio de libro de texto, no escribiré el código para reconstruir las posiciones de división reales.

Answer 4

Una solución dp en c ++:

int main()
{
    set<string> dict;
    dict.insert("12");
    dict.insert("123");
    dict.insert("234");
    dict.insert("12345");
    dict.insert("456");
    dict.insert("1234");
    dict.insert("567");
    dict.insert("123342");
    dict.insert("42");
    dict.insert("245436564");
    dict.insert("12334");

    string str = "123456712334245436564";

    int size = str.size();
    vector<int> dp(size+1, -1);
    dp[0] = 0;
    vector<string > res(size+1);
    for(int i = 0; i < size; ++i)
    {
        if(dp[i] != -1)
        {
            for(int j = i+1; j <= size; ++j)
            {
                const int len = j-i;
                string substr = str.substr(i, len);
                if(dict.find(substr) != dict.end())
                {
                    string space = i?" ":"";
                    res[i+len] = res[i] + space + substr;
                    dp[i+len] = dp[i]+1;
                }
            }
        }
    }
    cout << *dp.rbegin() << endl;
    cout << *res.rbegin() << endl;

    return 0;
}

Answer 5

Para formalizar lo que sugirió @MinhPham.

Esta es una solución de programación dinámica.

Dado un str cadena, deja

b [i] = verdadero si la subcadena str [0 ... i] (inclusive) se puede dividir en palabras válidas.

Prefiere un carácter inicial a str, por ejemplo!, Para representar la palabra vacía. str = "!" + str

El caso base es la cadena vacía, por lo que

b [0] = verdadero.

Para el caso iterativo:

b [j] = verdadero si b [i] == verdadero y str [i..j] es una palabra para todo i <j

Answer 6

A continuación hay una solución O (n ^ 2) para este problema.

void findstringvalid() {
string s = "itwasthebestoftimes";
set<string> dict;
dict.insert("it");
dict.insert("was");
dict.insert("the");
dict.insert("best");
dict.insert("of");
dict.insert("times");

vector<bool> b(s.size() + 1, false);
vector<int> spacepos(s.size(), -1);
//Initialization phase
b[0] = true; //String of size 0 is always a valid string
for (int i = 1; i <= s.size(); i++) {
    for (int j = 0; j <i; j++) {
       //string of size s[ j... i]
       if (!b[i]) {
           if (b[j]) {
              //check if string "j to i" is in dictionary
              string temp = s.substr(j, i - j);
              set<string>::iterator it = dict.find(temp);
              if (it != dict.end()) {
                  b[i] = true;
                  spacepos[i-1] = j;
              }
           }
        }
    }
}
if(b[s.size()])
    for (int i = 1; i < spacepos.size(); i++) {
        if (spacepos[i] != -1) {
            string temp = s.substr(spacepos[i], i - spacepos[i] + 1);
            cout << temp << " ";
    }
    }
}