?
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# Func: 计算偏移表
def calShiftMat(st):
dic = {}
for i in range(len(st)-1,-1,-1):
if not dic.get(st[i]):
dic[st[i]] = len(st)-i
dic["ot"] = len(st)+1
return dic
# 其他情况判断
if len(needle) > len(haystack):return -1
if needle=="": return 0
# 偏移表预处理
dic = calShiftMat(needle)
idx = 0
while idx+len(needle) <= len(haystack):
# 待匹配字符串
str_cut = haystack[idx:idx+len(needle)]
# 判断是否匹配
if str_cut==needle:
return idx
else:
# 边界处理
if idx+len(needle) >= len(haystack):
return -1
# 不匹配情况下，根据下一个字符的偏移，移动idx
cur_c = haystack[idx+len(needle)]
if dic.get(cur_c):
idx += dic[cur_c]
else:
idx += dic["ot"]
return -1 if idx+len(needle) >= len(haystack) else idx
?
class Solution:
def strStr(self,haystack:str,needle:str) ->
#计算偏移表
def calShiftMat(st):
dic = {}
for i in range(len(st) -1,-1,-1):
if not dic.get(st[i]):
dic[st[i]] = len(st) -i
dic["ot"] = len(st) +1
return dic
#其他情况判断
if len(needle) > len(haystack) : return -1
if needle == "": return 0
# 偏移表预处理
dic = calShiftMat(needle)
idx = 0
while idx +len(needle) <= len(haystack):
#带匹配字符串
str_cut = haystack[idx:idx+len(needle)]
#判断是否匹配
?
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
for (int i = 0; i + m <= n; i++) {
bool flag = true;
for (int j = 0; j < m; j++) {
if (haystack[i + j] != needle[j]) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
}
};
class Solution{
?
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
a=len(needle)
b=len(haystack)
if a==0:
return 0
next=self.getnext(a,needle)
j=-1
for i in range(b):
while j>=0 and needle[j+1]!=haystack[i]:
j=next[j]
if needle[j+1]==haystack[i]:
j+=1
if j==a-1:
return i-a+1
return -1
def getnext(self,a,needle):
next=['' for i in range(a)]
j=-1
next[0]=j
for i in range(1,len(needle)):
while (j>-1 and needle[j+1]!=needle[i]):
j=next[j]
if needle[j+1]==needle[i]:
j+=1
next[i]=j
return next
