在源串S中搜索目标串T时，利用串匹配的暴力求解方法，在求解的过程中，我们分析得到简化该问题求解过程的关键步骤，也即kmp算法的核心思想：如何在某趟S[i]和T[j]匹配失败时，下标i不回溯，下标j回溯到某个位置k，下一趟搜索时，从T[k]和S[i]开始比较。这样可以使得算法复杂度降低到O(n)，其中n为源串S的长度。 一、什么是真前缀和真后缀 真前缀就是对T[j]来说，使得T[0]~T[k-1