Por fin después de mucho batallar hemos hallado la contestación de este asunto que ciertos de nuestros lectores de esta web han presentado. Si tienes algún detalle que aportar no dudes en aportar tu comentario.
Solución:
Por qué se implementó c ++ string:: substr () no usa el algoritmo KMP (y no se ejecuta en O (N + M)) y se ejecuta en O (N * M)?
Supongo que te refieres find(), en vez de substr() que no necesita buscar y debe ejecutarse en tiempo lineal (y solo porque tiene que copiar el resultado en un nuevo string).
El estándar C ++ no especifica detalles de implementación y solo especifica requisitos de complejidad en algunos casos. Los únicos requisitos de complejidad en std::string las operaciones son eso size(), max_size(), operator[], swap(), c_str() y data() son todo tiempo constante. La complejidad de cualquier otra cosa depende de las elecciones realizadas por quien haya implementado la biblioteca que está utilizando.
La razón más probable para elegir una búsqueda simple en lugar de algo como KMP es evitar la necesidad de almacenamiento adicional. A menos que el string encontrar es muy largo, y el string buscar contiene una gran cantidad de coincidencias parciales, el tiempo necesario para asignar y gratis que probablemente sería mucho más que el costo de la complejidad adicional.
¿Eso está corregido en c ++ 0x?
No, C ++ 11 no agrega ningún requisito de complejidad a std::string, y ciertamente no agrega ningún detalle de implementación obligatorio.
Si la complejidad de la subestación actual no es O (N * M), ¿cuál es?
Esa es la complejidad del peor de los casos, cuando el string buscar contiene muchas coincidencias parciales largas. Si los personajes tienen una distribución razonablemente uniforme, entonces la complejidad promedio estaría más cerca de O(N). Por lo tanto, al elegir un algoritmo con una mayor complejidad en el peor de los casos, es posible que los casos más típicos sean mucho más lentos.
¿De dónde sacas la impresión de eso? std::string::substr() no usa un algoritmo lineal? De hecho, ni siquiera puedo imaginar cómo implementar de una manera que tenga la complejidad que citó. Además, no hay mucho algoritmo involucrado: ¿es posible que piense que esta función hace algo más de lo que hace? std::string::substr() solo crea un nuevo string comenzando en su primer argumento y usando el número de caracteres especificado por el segundo parámetro o los caracteres hasta el final del string.
Puede que te refieras a std::string::find() que no tiene requisitos de complejidad o std::search() que de hecho puede hacer comparaciones O (n * m). Sin embargo, esto les da a los implementadores la libertad de elegir entre un algoritmo que tiene la mejor complejidad teórica frente a uno que no necesita memoria adicional. Dado que la asignación de cantidades arbitrarias de memoria generalmente no es deseable a menos que se solicite específicamente, esto parece una cosa razonable.
FYI, el string:: Find tanto en gcc / libstdc ++ como en llvm / libcxx eran muy lentos. Mejoré ambos de manera bastante significativa (en ~ 20x en algunos casos). Es posible que desee verificar la nueva implementación:
GCC: PR66414 optimizar std ::string:: buscar https://github.com/gcc-mirror/gcc/commit/fc7ebc4b8d9ad7e2891b7f72152e8a2b7543cd65
LLVM: https://reviews.llvm.org/D27068
El nuevo algoritmo es más simple y utiliza funciones de ensamblaje optimizadas a mano de memchr y memcmp.