sunday 算法

字符串匹配--sunday 算法

听说这个算法比kmp效率还高，而且重要的是还好理解，所以就.....

好了，sunday算法还真的很好理解，用下面的例子来说明吧：

j                                k

t h i s   i s   a   s i m p l e   e x a m p l e .

e x a m p l e

i

这个例子中上面的字符串是待查找字符串，下面的是子串。sunday的思想是这样的：

首先i,j两个指针指示的位置（也就是从头开始匹配），当发现失配的时候就判断子串的后一位在母串的字符（在上面的例子中是空格字符，k标记处）是否在子串中存在？如果存在则将该位置和子串中的该字符对齐，在从头开始匹配。如果不存在就将子串向后移动，和母串k+1处的字符对齐，再进行匹配。重复上面的操作直到找到，或母串被找完结束。

对于上面的例子继续进行，刚才说了失配，并且空格在子串中不存在，所以子串向后移动，子串的第一个字符和母串的k+1位置的字符对齐，如下图：

j                                 k

t h i s   i s   a   s i m p l e   e x a m p l e .

e x a mp l e

i

这次比较还是失配，但是k位置的e在子串中出现了，而且第一个就是，最后一个也是，这时候一定要将子串中靠后出现的e和母串中的e对齐如下图：

j                               k

t h i s   i s   a   s i m p l e   e x a m p l e .

e x am p l e

i

为什么是最靠后的一个呢？如果这里用第一个e来和母串中的e对齐，就有可能将中间出现的可匹配字符串空过去。

同上这次还是失配，所以还要再进行一次。

t h i s   i s   a   s i m p l e   e x a m p l e .

ex amp l e

这次就匹配成功了。

下面是一段代码供大家参考：

11 int in_dst(const char word, const char *dst)

12 {

13 int i = strlen(dst) - 1;

14

15 while (dst[i] != '\0')

16 {

17 if (dst[i] == word)

18 return (strlen(dst) - i);

19

20 i--;

21 }

22

23 return -1;

24 }

25

26

27 int sunday(const char *src, const char *dst)

28 {

29 int SrcLenth = strlen(src), DstLenth = strlen(dst);

30 int j = 0, i = 0, pos;

31

32 while (j < SrcLenth)

33 {

34 i = 0;

35 while (src[j+i] == dst [i])

36 {

37 i++;

38 continue;

39 }

40

41 if (dst[i] == '\0')

42 {

43 printf("%d~%d\n", j, j+DstLenth-1);

44 }

45

46 if ((pos = in_dst(src[j+DstLenth], dst)) != -1)

47 {

48 j += pos;

49 }

50 else

51 {

52 j += (DstLenth + 1);

53 }

54 }

55 }