lej*_*lot 8
虽然算法可能是 O(N)，但您的实现似乎不是线性的，至少对于模式的多次重复而言不是，因为
s = s[:i - 2 * len(p) + shift] + c + s[i - len(p) + shift:]
这是 O(N) 本身。因此，如果您的模式在一个字符串中发生 N 次，那么您的实现实际上是 O(N^2)。
请参阅以下时间以了解您的算法的缩放时间，这确认了二次形状
LENGTH TIME
------------
100000 1s
200000 8s
300000 31s
400000 76s
500000 134s
更多推荐
str,replace
发布评论