一、 KMP算法
当判断模式串在主串中,出现过几次。标记出模式串重复
0 | 1 | 2 | 3 | 4 | 5 | 6 |
| a | b | C | a | b | a |
-1 | 0 | 0 | 0 | 1 | 2 | 1 |
如图,模式串为‘abcaba’,第一行表示在模式串中的位置,第二行表示在对应位置上的字符,第三行表示若在该位置失配了,它返回的位置。
假如主串为‘abcdabcad’,
主串 | 模式串 | 模式串的位置 | 是否匹配 |
a | a | 1 | 匹配 |
b | b | 2 | 匹配 |
c | c | 3 | 匹配 |
d | a | 4 | 不匹配 |
d | a | 1 | 不匹配 |
d | 空 | 0 | 不匹配 |
a | a | 1 | 匹配 |
b | b | 2 | 匹配 |
c | c | 3 | 匹配 |
a | a | 4 | 匹配 |
d | b | 5 | 不匹配 |
d | b | 2 | 不匹配 |
d | 空 | 0 | 不匹配 |
所以主串中没有模式串。
好处:主串的位置不需要移动。
计算KMP数组的方法:
从头开始,寻找当前位置至开始判断两边的字符重复的个数记录入当前位置的KMP数组中。
程序:
next[0] := -1;
For i:=1 To n1 Do Begin
j := next[i-1];
While (j >=0) And (a[i] <> a[j+1]) Do j := next[j];
next[i] := j +1;
End;
二、 字典树
将多个字符串用一个串储存,方便找出最长公共串。
比如说有11个子串
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
将它们表现成字典树的形式为
这样就很容易求出最长公共串或其他
方法:
建立一个串(有一个从‘a’至‘z’的数组和其他)
由第一个字符串循环到最后一个字符串,
判断字符串当前是否出现过,
若是则链的位置向下移一个位置
否则标记此字符在当前位置出现过,并记录。
程序:
Type
Link = ^obj1;
obj1 = Record
a:Array['a'..'z']Of Link;
num:Longint;
End;
Procedure make;
Var
p1, p: Link;
i: Longint;
Begin
p := trie;
l :=length(str1);
For i:=1 To lDo Begin
Ifp^.a[str1[i]] <> nil Then Inc(p^.a[str1[i]]^.num)
Else Begin
new(p1);
Forch:='a' To 'z' Do p1^.a[ch] := nil;
p1^.num :=1;
p^.a[str1[i]] := p1;
End;
p :=p^.a[str1[i]];
End;
End;
联系客服