难度：容易
1. Description
13. 字符串查找
2. Solution
用kmp算法
- c++
c++代码的测试用例有问题，无法通过。
有一个测试用例是NULL,NULL，string类型变量不能被赋值为NULL。
下面的python代码思路完全一样，是可以通过的。
class Solution {
public:
/**
* @param source:
* @param target:
* @return: return the index
*/
int strStr(string &source, string &target) {
// Write your code here
// if(target == NULL || source == NULL){
// return -1;
// }
int len_s = source.size();
int len_t = target.size();
if(len_t==0){
return 0;
}
if(len_s==0&&len_t!=0){
return -1;
}
int next[1000]={0};
for(int i=1;i<len_t;i++){
if(target[i]==target[next[i-1]]){
next[i] = next[i-1]+1;
}else if(target[i]==target[0]){
next[i]=1;
}
}
int i=0,j=0;
for(;i<len_s&&j<len_t;){
if(source[i]==target[j]){
i++;
j++;
}else if(source[i]!=target[j]){
if(j!=0){
j = next[j-1];
}else{
i++;
}
}
}
if(j==len_t){
return i-j;
}else{
return -1;
}
}
};
- python
class Solution:
"""
@param source:
@param target:
@return: return the index
"""
def strStr(self, source, target):
# Write your code here
if source is None or target is None:
return -1;
len_s = len(source)
len_t = len(target)
if len_t==0:
return 0
elif len_s==0:
return -1
# 计算next数组
next = [0 for _ in range(len_t)]
for i in range(1,len_t):
if target[i] == target[next[i-1]]:
next[i] = next[i-1]+1
elif target[i] == target[0]:
next[i]=1
# kmp
i,j=0,0
while(i<len_s and j<len_t):
if source[i]==target[j]:
i+=1
j+=1
elif source[i]!=target[j]:
if j!=0:
j = next[j-1]
else:
i+=1
if j==len_t:
return i-j
else:
return -1
