[关闭]
@songpfei 2016-06-01T15:08:27.000000Z 字数 2174 阅读 641

数据结构


1 串的定义

串(string):是零个或多个字符串组成的有限序列,又名叫字符串。

2. 朴素模式匹配算法

子串的定位操作通常称作串的模式匹配

  1. using namespace std;
  2. /**************************
  3. 函数功能:串的朴素匹配
  4. 参数说明:S:主串 T:子串
  5. pos:开始查找子串的初始位置
  6. 说明:返回子串T在主串S中第pos个字符之后的位置。若不存在,则返回值为0
  7. **************************/
  8. int Index(string s, string t, int pos)
  9. {
  10. int i = pos;//主串的起始索引位置
  11. int j = 0;//子串的起始索引位置
  12. while (i < s.length() && j < t.length())
  13. {
  14. if (s[i] == t[j])
  15. {
  16. ++i;
  17. ++j;
  18. }
  19. else
  20. {
  21. i = i - j + 2;//返回上次匹配的下一位置
  22. j = 0;
  23. }
  24. }
  25. if (j == t.length())
  26. return i - t.length();
  27. else
  28. return 0;
  29. }

3. KMP模式匹配算法

D.E.Knuth、J.H.Morris和V.R.Pratt(其中,Knuth和Partt共同研究,Morris独立研究)发表一个模式匹配算法,可以大大避免重复遍历的情况,称之为克努特--莫里斯--普拉特算法,简称KMP算法

3.1 关于前缀及后缀

参照:http://kb.cnblogs.com/page/176818/
"前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,
  - "A"的前缀和后缀都为空集,共有元素的长度为0;
  - "AB"的前缀为[A],后缀为[B],共有元素的长度为0;
  - "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;
  - "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;
  - "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;
  - "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;
  - "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。
  

3.2《算法导论》第32章中KMP算法的伪代码:

  1. 计算匹配的位置
  1. KMP-MATCHER(T,P)//T:主串 P:子串(模式字符)
  2. n=T.length
  3. m=p.length
  4. π=COMPUTE-PREFIX-FUNCTION(P)
  5. q=0 //number of characters matched
  6. for i=1 to n //scan the text from left to right
  7. while q>0 and P[q+1]≠T[i]
  8. q=π[q] //next characters does not match
  9. if P[q+1]==T[i]
  10. q=q+1 //next character matches
  11. if q==m //is all of P matched ?
  12. print"Pattern occours with shift" i-m
  13. q=π[q] //look for the next match
  1. 计算前缀函数
  1. COMPUTE-PREFIX-FUNCTION(P)
  2. m=P.length
  3. let π[1...m] be a new array
  4. π[1]=0
  5. k=0
  6. for q=2 to m
  7. while k>0 and P[k+1]≠P[q]
  8. k=π[k]
  9. if P[k+1]==P[q]
  10. k=k+1
  11. π[q]=k
  12. return π

3.C语言KMP算法实现

  1. /*计算前缀函数数组 pattern*/
  2. int* ComputePreFix(const string &P)
  3. {
  4. int m = P.length();
  5. int *pattern = new int[m];
  6. pattern[0] = 0;
  7. int k = 0;
  8. for (int q = 1; q < m; q++)
  9. {
  10. while (k>0 && P[k] != P[q])
  11. k = pattern[k - 1];
  12. if (P[k] == P[q])
  13. k += 1;
  14. pattern[q] = k;
  15. }
  16. return pattern;
  17. }
  18. /* KMP法进行字符串匹配*/
  19. void KMP_matcher(const string &T, const string &P)
  20. {
  21. int n = T.length();
  22. int m = P.length();
  23. int* pattern = ComputePreFix(P);
  24. int q = 0;//已匹配的字符串个数
  25. for (int i = 0; i < n; i++)
  26. {
  27. while (q>0&&P[q]!=T[i])
  28. q = pattern[q - 1];
  29. if (P[q] == T[i])
  30. q += 1;
  31. if (q == m)
  32. {
  33. cout << "Pattern occours with shift " << i - m+1;
  34. q = pattern[q - 1];
  35. }
  36. }
  37. delete pattern;
  38. pattern = NULL;
  39. }
  1. int main()
  2. {
  3. string T = "goodababacgooleababaca";
  4. string P = "ababaca";
  5. KMP_matcher(T, P);
  6. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注