KMP推导与C语言实现

0.说明 由于大部分文章直接从算法入手,即使配合丰富的动图,理解起来也有一些难度。在自己理解和实现后,用推导的思路聊一聊KMP。 当进行子字符串查找时,最简单的方法是尝试将母字符串的每一位依次看作首位,和目标字符串进行逐字符对比。这样非常易懂,但效率偏低。 如果母字符串长度为m,目标字符串长度为n,算法时间复杂度可能达到m*n。在基因工程等(字符集较少,相对容易大段重复,且目标串和母串都非常长)特殊情况下这样的时间复杂度是较难接受的。这时非常需要思考如何进行优化。 1.寻找可跳过的场景 相对容易想到(其实也很难)的一个方向是跳过一些无需重复的检查的场景,那我们先找一找有哪些场景可以跳过。 当我们有 开始,进行逐字符比较,从 对比至 发现不一致了。按最简单的做法,我们需要改变首字符位置重新匹配,如下 周而复始,可以发现迟早我们将对比至 而这个场景和当初场景1时的 是多么的相似啊(都将需要对比abc,且都能匹配上)。如果我们能跳过刚才这里已经对比过的abc。如果能避免重复对比,直接进行 至少能省下对比abc的时间。嗯,虽然看起来优化价值不大,如果能很低成本做,到至少还是稍有价值的(省了三次对比)。 …

全文KMP推导与C语言实现

泊松分布推导

当我们知道任意 \(T\) 时间内,某事件发生的期望次数是 \(\lambda\) 。 且知道事件每次发生都是独立的,没有相关影响,我们应该如何计算 \(T\) 时间内事件发生次数的概率分布呢? 我们可以考虑将这段 \(T\) 时间进行均匀划分,比如划分为 \(n\) 段。 那么显然,每段发生事件的期望次数为: …

全文泊松分布推导