子串：由任何连续字符组成的子序列（包括空串）称为子串。 例如，‘abcde子串有： 真子串是指不包含自己的所有子串。 子串位置：主串中子串第一个字符的位置 串相等:当两个串的长度相等，每个对应位置的字符相同时，这两个串是相等的。 基本操作： 1、串赋值 2、串比较 3、求串长 4、串连结 5、求子串 6、串拷贝 7、串判空 8、清空串 9.子串的位置 10、串替换 11、子串插入 12、子串删除 13、串销毁
算法目的:确定子串(模式串)在主串中首次出现的位置(定位)。 算法种类，BF算法(穷举)，KMP算法。 BF算法:算法思路是从S的每个字符开始依次匹配T的字符。
KMF算法： 见此链接： KMP算法详解 如图， 1.主串B不同于模式串A。此时，判断模式串ABBAB部分匹配值(前缀和后缀共有元素最长长度)判断为2，即AB。 2.有两种解释方法。第一种是将前缀的原始位置移动到后缀的位置 第二种就是移动的位数=匹配的字符数（ABBAB）-部分匹配值（AB）=3.移动三个位置到达第二个判断点。 然后又开始找， 可见主串位置B与模式串位置A不同，然后1判断ABBABA部分匹配值1(A）。 然后又移动ABBABA（6）-A （1）= 5 此时超过字符串长度，因此不一致。
next数组：当主串与模式串的某个字符不匹配时，模式串应返回
求取next方法:这个写程序可以遵循这个想法
python思路：
def nextArray(s): '''计算next数组组函数 #初始化next[j]数组 nextA = [0]#即j=1时，next[j]=0 for i in range(1,len(s)):#range如果长度为2，则返回左闭右开。i只能=1 forwardS = s[0:i]#这句话表明取的是：例如ABC',S='A','AB即取模式串前的字符串 fowardL = len(forwardS) if (len(forwardS) ==1):#当模式串前只有一个字符时 nextA.append(1) else:#当模式串前有多个字符时，取模式串前的字符串前后交叉 j = fowardL -1 count = 1 #即当前后缀没有交集时，默认为其他情况，next[j]=1 while j>0: if forwardS[0:j]==forwardS[fowardL-j:fowardL]:#如果有交集，cout = j 1.这里不能直接做forwardS[j:fowardL] #因为这个比较A,AB,ABC与BCD,CD,D，不对称，所以交换位置 count span class="token operator">= j+1
break
j = j -1 #跳出循环条件
nextA.append(count)
return nextA
s = 'ABAABCAC'
a =nextArray(s)
print(a)
结果如下：
接下来求取nextval：
def nextVal(s):
nextA = nextArray(s)
nextV = nextA[:]
if len(s)>=3:
for i in range(2,len(s)):
if s[i] ==s[nextA[i]-1]:
nextV[i]= nextV[nextA[i]-1]
return nextV
结果如下：
def index_KMP(s,t):
lenS = len(s)
lenT = len(t)
nextV = nextVal(t)
print(b)
i = 0
j = 0
while i<lenS and j <lenT:
if s[i] == t[j]:#相同，依次往下循环
i += 1
j += 1
else:
j = nextV[j-1]#如果不相同，让模式串的位置移动到后缀的位置
if j>=len(t):
return i - j
else:
return 0
s = 'aaaaab'
t = 'aaab'
a =nextArray(t)
b = nextVal(t)
c = index_KMP(s,t)
print(c)
结果如下： 补充BF算法
def indexBF(s,t):
lenS = len(s)
lenT = len(t)
i = 0
j = 0
while i<lenS and j <lenT:
#如果A串与B串第一个字符相同，两个都往后移
#如果不相同，A回溯，B回到首位
if s[i]==t[j]:
i+=1
j+=1
else:
i= i-j+2
j = 1
#如果j超出原始成都，返回i-lenT位置
if j>=lenT:
return i-lenT
else:
return 0
s = 'aaaaab'
t = 'aaab'
b = indexBF(s,t)
print(b)
测试结果：