算法总结

 

一、  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 l Do Begin

    If p^.a[str1[i]] <> nil Then Inc(p^.a[str1[i]]^.num)

    Else Begin

      new(p1);

      For ch:='a' To 'z' Do p1^.a[ch] := nil;

      p1^.num := 1;

      p^.a[str1[i]] := p1;

    End;

    p := p^.a[str1[i]];

  End;

End;