实现 strStr() 函数
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = "hello", needle = "ll"
输出：2
示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1
示例 3：
输入：haystack = "", needle = ""
输出：0
提示：
0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成
本题是经典的字符串单模匹配的模型，因此可以使用字符串匹配算法解决，常见的字符串匹配算法包括暴力匹配、Knuth-Morris-Pratt 算法、Boyer-Moore 算法、Sunday 算法等，本文将讲解 KMP （Knuth-Morris-Pratt ）算法。
朴素暴力破解法
简单的循环判断即可。
这里用一个 flagArray ， 记录 needle 每个字符是否在 haystack 中。
代码
class Solution {
fun strStr(s: String, x: String): Int {
if (x.isEmpty())
return 0
val sArray = s.toCharArray()
val xArray = x.toCharArray()
val width = x.length
for (i in 0..(s.length - 1)) {
if (i + width > s.length) {
break
}
// 针对每一个 i， 遍历 x
val flagArray = BooleanArray(width, { false })
// 注意: 这地方的区间 [i, i + width - 1]
(i..(i + width - 1)).forEachIndexed { index, k ->
if (sArray[k] == xArray[index]) {
flagArray[index] = true
}
}
if (flagAllTrue(flagArray)) {
return i
}
}
return -1
}
fun flagAllTrue(flagArray: BooleanArray): Boolean {
var flag = true
flagArray.forEach {
flag = flag && it
}
return flag
}
}
时间复杂度: O (m * n)
空间复杂度: O (m)
KMP 算法
KMP 算法的核心思想是在遍历模式串的过程中，把模式串的对称前后缀（等缀）部分记录下来，下一轮比对模式串的时候，直接把上一次已经比对的前缀（=后缀）部分跳过，直接来到 next（j）。
动画图示：
当下标为 i=5, j=5 的时候，发现 s[i]!=x[j], 接下来，要开始回溯。
首先，检查之前已经匹配成功的部分：aabaa（ 此时，要看next（4）= 2 ），判断是否存在相同的「前缀」和「后缀」;
if 存在( 这里是 aa )，则跳转到「前缀」的下一个位置( aabaaf )继续往下匹配。
前一个字符的前缀表的数值是2， 所有把下标移动到下标2的位置继续比配。 可以再反复看一下上面的动画。
定义:滑动步长 π(i) 函数如下：
s[0..i]前后等缀最大长度。
e.g. 模式串：x = aabaaf
π (0) = a = 0
π (1) = aa = 1
π (2) = aab = 0
π (3) = a ab a = 1
π (4) = aabaa = 2
说明一下：比如说，当模式串x 跟 s 的第 0..4 个字符均相等，那么如果第 5 个字符不相等，下一轮比对就可以直接从 aa
baa 中的baa 处开始比对了。 因为，前面的aabaa跟后面的aabaa, 在上一轮比对的过程中已经匹配过，是相等的。)
π (5) = aabaaf = 0
这个 π(i) 函数也叫前缀表（prefix table）。前缀表有什么作用呢？ 前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
实现 π(i) 函数 之后，按照上面动画演示的算法步骤实现源代码即可。
如果输入的模式串为 aabaaf，对应的 next 为 0 1 0 1 2 0，（其实这就是前缀表的数值了）。
那么用这样的next数组也可以用来做匹配。实现代码如下：
class Solution {
fun strStr(s: String, x: String): Int {
val m = x.length
val n = s.length
if (x.isEmpty()) {
return 0
}
var j = 0
// 模式串的最大等缀长度表
val next = getNext(x)
// 遍历 s[n]
(0..n - 1).forEach {
val i = it
while (j > 0 && s[i] != x[j]) {
j = next[j - 1]
}
if (s[i] == x[j]) {
j++
}
if (j == m) {
return i - m + 1
}
}
return -1
}
fun getNext(s: String): IntArray {
val next = IntArray(s.length)
var j = 0
next[0] = j
for (i in 1 until s.length) {
while (j > 0 && s[i] != s[j]) {
j = next[j - 1]
}
if (s[i] == s[j]) {
j++
}
next[i] = j
}
return next
}
}
如何求解前缀函数？
上面的 getNext(s: String) 函数的算法思想可以说是“艺术”了（一般人真的想不到，想必这就是大师为什么是大师了吧！）：
时间复杂度: O (m + n)
空间复杂度: O (m)
KMP 算法源代码
/**
* pi(k) 函数: 递归计算字符串的最大公共前后缀的长度 max common prefix suffix length
*/
fun pi(j: Int, pattern: String): Int {
if (j == 0) return 0
for (k in 1 until pattern.length) {
while (pattern[j] != pattern[pi(j - 1, pattern)] && pi(j - 1, pattern) > 0) {
return pi(pi(j - 1, pattern) - 1, pattern)
}
if (pattern[j] == pattern[pi(j - 1, pattern)]) {
return pi(j - 1, pattern) + 1
}
}
return 0
}
fun kmp(text: String, pattern: String): Int {
val m = pattern.length
val n = text.length
if (pattern.isEmpty()) {
return 0
}
// j: the current index of pattern
var j = 0
(0 until n).forEach {
// i: the current index of text
val i = it
while (j > 0 && text[i] != pattern[j]) {
j = pi(j - 1, pattern = pattern)
}
if (text[i] == pattern[j]) {
j++
}
if (j == m) {
return i - m + 1
}
}
return -1
}
fun main() {
var text = "addaabbcaabffffggghhddabcdaaabbbaab"
var pattern = "aabbcaab"
for (i in 0 until pattern.length) {
print("${pi(i, pattern)} ")
}
println("\nKMP subtring search algorithm:")
var index = kmp(text, pattern)
println("$pattern is the substring of $text, the index is: $index")
text = "hello"
pattern = "ll"
for (i in 0 until pattern.length) {
print("${pi(i, pattern)} ")
}
println("\nKMP subtring search algorithm:")
index = kmp(text, pattern)
println("$pattern is the substring of $text, the index is: $index")
text = "aaaaa"
pattern = "bba"
for (i in 0 until pattern.length) {
print("${pi(i, pattern)} ")
}
println("\nKMP subtring search algorithm:")
index = kmp(text, pattern)
println("$pattern is the substring of $text, the index is: $index")
}
网友评论