nam*_*ked 9 java string algorithm
我只是看着Java String类的.indexOf()方法的实现,似乎代码的作者使用强力算法来查找给定字符串中的子字符串.也就是说,该方法在O(mn)中运行,其中m和n分别是源和目标字符串的长度.
为什么作者没有使用像Rabin-Karp这样的更有效的算法,如果提供了良好的哈希函数,它的运行时复杂度为O(m + n)？
我可能会错过这个实现原因背后的完整知识,因此想要了解.
tem*_*def 15
我不确定为什么要做出这个决定,但是如果我猜测它可能是因为对于小模式字符串(一个非常常见的用例),天真的强力算法可能同样快,如果不是比一些渐近的更快更快的算法,如Rabin-Karp,Boyer-Moore或Knuth-Morris-Pratt.这似乎是一个合理的默认算法,因为在很多情况下,您将搜索小字符串以寻找小模式,而强大的匹配设置的开销可能与天真方法的运行时相当.
也就是说,Java规范中没有任何地方要求使用这种算法.他们可以很容易地选择Rabin-Karp作为默认算法.
他们可能选择这种方法的另一个原因是因为如果你想进行快速文本搜索,正则表达式库提供更快的字符串匹配和更强大的搜索功能.默认情况下为用户提供简单的强力算法,并在需要时切换到更强大的工具集,这似乎是平衡渐近效率和实际效率的好方法.
我假设你的意思是indexOf或包含而不是substring.子串是O(1)
通常简单的代码运行得更快 例如,创建对象的代码通常运行得慢得多.
你为什么不尝试自己实现它,看看它是否更快.如果是,您可以建议他们改进方法.