leetcode 28. Implement strStr() running time 问题分析

原题如下
Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1
对于这个题目,根据算法导论的分析，如果用naive算法,runningtime 应该是O((n-m+1)*m)
如果用kmp算法,preprocess + match 总共的runningtime 应该是O(m)+O(n)~O(n＋m)
那么KMP vs naive 哪个running time 更小呢？
f(m,n)=n+m-(n-m+1)*m
=m^2-n(m-1)
假设n＋m<(n-m+1)*m
=>   f(m,n)<0
=>  m^2<n(m-1)
=>  n>m^2/(m-1)
n＝m时 很明显 n< m^2/(m-1);
n=m+1 时 n－m^2/(m-1)＝m+1－m^2/(m-1)＝－1/(m-1)<0 ＝> n< m^2/(m-1);
n>=m+2 时 n－m^2/(m-1)>=m+2－m^2/(m-1)=(m-2)/(m-1)  有 m>2 时 n>m^2/(m-1)
而在leetcode 我用两种方法提交过，发现，KMP算法的running time 要比 朴素算法长。
根据上述推理，我大胆推测，可能是leetcode的test case存在大量的 n=m+1 的情况导致 用 朴素算法 的running time 反而比KMP算法的小。

欢迎大家拍砖指正，踊跃讨论～