KMP算法
KMP算法
字符串匹配问题
字符串匹配问题场景
- 有一个字符串str1 = “abcdefg” 和 str2 = “def”
- 现在要判断str1 是否含有str2，如果存在，就返回第一次出现的位置，如果没有，则返回-1
暴力匹配算法
如果用暴力匹配的思路，并假设现在str1 匹配到i位置，字符串str2匹配到j位置，则有：
- 如果当前字符串匹配成功（即 str1[i] == str2[j]） , 则 i++，j++，继续匹配下一个字符
- 如果匹配失败（即 str1[i] != str2[j]），令 i = i - ( j - 1)，j = 0。相当于每次匹配失败时，i回溯，j被置为0.
- 用暴力方法解决的话，就会有大量的回溯，每次只移动一位，若匹配不成功，移动到下一位接着判断，浪费了大量的时间。 -
你可能感兴趣的文章
0
赞
热门推荐
-
2、 - 优质文章
-
3、 gate.io
-
8、 golang
-
9、 openharmony
-
10、 Vue中input框自动聚焦