原题
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1:
输入: haystack = “hello”, needle = “ll”
输出: 2
示例 2:
输入: haystack = “aaaaa”, needle = “bba”
输出: -1
说明:
当 needle
是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当 needle
是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
解法
JDK API
在leetcode上,当然可以投机取巧地使用String.indexof()方法,不用重复造轮子:
class Solution {
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle);
}
}
但这是一个经典的字符串精准模式匹配问题,历史上出现过很多解决这个问题的算法,掌握它们的思想还是有必要的:
BF算法(朴素算法)
思想
这是最直观、最简单的算法。从主串的第start个字符起和模式的第1个字符比较,如果相等继续逐个比较后续字符。比较过程中一旦发现不相等的情况,则回溯至主串中的第start+1个字符位置处,重新与模式P的字符进行比较。该算法效率较低。
代码
class Solution {
public int strStr(String haystack, String needle) {
int mainLen = haystack.length();
int subLen = needle.length();
if(needle.equals("")) return 0;//注意模式字符串为空的情况
for(int i=0;i<mainLen;i++){
for(int j =0;j<subLen;j++){
if(!(i+j<mainLen)) return -1;//主串下标超出
if(!(haystack.charAt(i+j)==needle.charAt(j))) break;
else if(j == subLen-1) return i;//完全匹配,返回主串下标
}
}
return -1;
}
}
算法的复杂度为O[(i-j)j]
MP算法
思路
指针不回溯,利用已得到的“部分匹配”结果,将模式向右“滑动”若干位置后继续比较。
参考下面给出的示例:
haystack :"cdnidnidsm"
needle:"nidsm"
按照BF算法的思想,在比较haystack[2]
和needle[0]
时,两个字符相等,然而比较到haystack[5]
和needle[3]
的时候两个字符不等,于是回溯继续向后比较haystack[3]
和needle[0]
。可是既然能确定haystack[2]-haystack[4]
与needle[0]-needle[2]
是完全对应的。那么比较haystack[3]
和needle[0]
实际上相当于比较needle[1]
和needle[0]
。并且我们知道needle中前三个字符都是不同的。所以只需要从haystack[5]
处继续跟needle[0]
比较就行了。并且needle中字符的这些关系完全是一开始就可以确定的。
我们称记录模式字符串中各个字符之间关系的函数为失效函数。
失效函数的定义域是模式字符串在“失配”前匹配的字符串个数。取值j属于0~Len(P)-1
获取失效函数的方法:
失效函数的取值k满足P0P1…Pk = Pj-kPj-k+1…Pj。如果不存在这个k值,取-1。
直观的看k就是模式字符串前j个字符是否存在前k+1位等于后k+1位。
nidsm的失效函数为:
j | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
p(j) | n | i | d | s | m |
k | -1 | -1 | -1 | -1 | -1 |
再举一个例子,caatcat的失效函数为:
j | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
p(j) | c | a | a | t | c | a | t |
k | -1 | -1 | -1 | -1 | 0 | 1 | -1 |
得到了失效函数后,即可使用MP算法进行匹配。假设在某一轮比较中,失配的情况发生在模式P的第j位,如果j=0,进行下一轮比较时,目标指针向后移动一位,模式的起始比较地址回到P0,其他情况进行下一轮比较时,目标指针不发生回溯,而模式P的起始比较地址为j-1对应的失效函数的值+1。
当然也可以把这个值提前算出来便成为了Next()函数:
j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
p(j) | c | a | a | t | c | a | t | |
Next(j) | -1 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
Next(7)可以用于继续匹配(可能要求找出所有匹配的子字符串)。
代码
class Solution {
//获取next函数
public int[] next(String needle){
int len = needle.length();
int i = 0;
int j = -1;
int[] next = new int[len+1];
next[0] = -1;
while(i < len){
while( j > -1 && needle.charAt(i)!=needle.charAt(j))
j = next[j];//j会有一个传递的效果,必须前一个i对应的j是1,下一个i对应的j才能是2。如果遇到不同的字符则j清零
next[++i] = ++j;
}
return next;
}
public int strStr(String haystack, String needle) {
int mainLen = haystack.length();
int subLen = needle.length();
if(needle.equals("")) return 0;//注意模式字符串为空的情况
if(mainLen<subLen) return -1;
int[] next = next(needle);
int i = 0;
int j = 0;
while(j < mainLen){
while(i>-1 && needle.charAt(i) != haystack.charAt(j))
i = next[i];
i++;
j++;
if(i >= subLen){
return j-i;
}
}
return -1;
}
}
KMP算法
思路
在MP算法的基础上,还要避免最长前缀之后的那个字符不等于原来失配的那个字符。
下面在已知mpNext表的情况下,给出建立kmpNext表的规则。这个规则分为四种情况:
- 如果mpNext[j] = 0且Pj = P0,则令kmpNext[j] = -1。
- 如果mpNext[j] = 0且Pj ≠ P0,则令kmpNext[j] = 0。
- 如果mpNext[j] ≠ 0且Pj ≠ PmpNext[j],则令kmpNext[j] = mpNext[j]。
- 如果mpNext[j] ≠ 0且Pj = PmpNext[j],则用mpNext[j]的值替换原来mpNext[j]中的j值,直到情况转换为前3种情况的一种,进而递归地求解kmpNext[j]。
j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
p(j) | c | a | a | t | c | a | t | |
mpNext(j) | -1 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
kmpNext(j) | -1 | 0 | 0 | 0 | -1 | 0 | 2 | 0 |
代码
class Solution {
//获取kmpNext数组
public int[] next(String needle){
int len = needle.length();
int i = 0;
int j = -1;
int[] next = new int[len+1];
next[0] = -1;
while(i < len-1){
while( j > -1 && needle.charAt(i)!=needle.charAt(j))
j = next[j];
i++;
j++;
if(needle.charAt(i) == needle.charAt(j))
next[i] = next[j];
else
next[i] = j;
}
return next;
}
public int strStr(String haystack, String needle) {
int mainLen = haystack.length();
int subLen = needle.length();
if(needle.equals("")) return 0;//注意模式字符串为空的情况
if(mainLen<subLen) return -1;
int[] next = next(needle);
int i = 0;
int j = 0;
while(j < mainLen){
while(i>-1 && needle.charAt(i) != haystack.charAt(j))
i = next[i];
i++;
j++;
if(i >= subLen){
return j-i;
}
}
return -1;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode28-%e5%ae%9e%e7%8e%b0strstr/