如题,对于第2个测试点,本地与输出一致但提交会错误
def initialize(pattern):
""" 计算模式字符串并初始化LPS数组 """
if(type(pattern) != str):
return None
pattern = str(pattern)
LEN = len(pattern)
LSPArr = [0]*LEN
moudleArr_index = 0
targetArr_index = 1
while(targetArr_index<LEN):
if(pattern[targetArr_index]==pattern[moudleArr_index]):
LSPArr[targetArr_index]=moudleArr_index+1
moudleArr_index+=1
targetArr_index+=1
else:
if(LSPArr[moudleArr_index]==0):
LSPArr[targetArr_index]=0
targetArr_index+=1
moudleArr_index=0
else:
moudleArr_index=LSPArr[moudleArr_index-1]
return LSPArr
def KMP(moudle_str,target_str):
""" 获取模式字符串和匹配串并初始化 """
index_arr=[]
LSP_arr=initialize(moudle_str)
moudle_len=len(moudle_str)
target_len=len(target_str)
target_index=0
moudle_index=0
while(target_index!=target_len):
if(moudle_str[moudle_index]==target_str[target_index]):
moudle_index+=1
target_index+=1
if(moudle_index==moudle_len):
index_arr.append(target_index-moudle_index+1)
moudle_index=LSP_arr[moudle_index-1]
else:
if(moudle_index==0):
moudle_index+=1
target_index+=1
else:
moudle_index = LSP_arr[moudle_index-1]
return index_arr,LSP_arr
if __name__ == '__main__':
target_str = input()
moudle_str = input()
my_index_arr,my_LSP_arr=KMP(moudle_str,target_str)
for index in my_index_arr:
print(index)
for index in my_LSP_arr:
print(index,end=' ')