标题:C++ String的find()成员函数 出处:Felix021 时间:Thu, 21 Aug 2008 14:53:28 +0000 作者:felix021 地址:https://www.felix021.com/blog/read.php?1101 内容: 摘自boost库的文档: Currently the library contains only naive implementation of find algorithms with complexity O(n * m) where n is the size of the input sequence and m is the size of the search sequence. There are algorithms with complexity O(n), but for smaller sequence a constant overhead is rather big. For small m < < n (m by magnitude smaller than n) the current implementation provides acceptable efficiency. Even the C++ standard defines the required complexity for search algorithm as O(n * m). It is possible that a future version of library will also contain algorithms with linear complexity as an option。 也就是说string::find()提供的是O(m*n)的效率,不是KMP的O(n),很汗。。。 Generated by Bo-blog 2.1.0