鱼C论坛

 找回密码
 立即注册
查看: 2778|回复: 0

[学习笔记] 《数据结构和算法》——KMP算法实现

[复制链接]
发表于 2017-8-3 19:12:57 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
利用一个next数组存储匹配串每一个位置的回溯下标,当用匹配串与被匹配串进行逐个比较时,若出现匹配错误,可以利用next数组快速回溯。
next数组:当前缀和后缀一致时,记录一次下标;若不一致,固定后缀,回溯前缀直至最开始的下标0,记录下标1,表示需要从头开始匹配。利用next数组我们可以快速地根据匹配串中重复的部分减少匹配次数。
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<string>
  4. #include<iostream>
  5. using namespace std;

  6. void GetNext(char T[], int next[])
  7. {
  8.         int i=1, j=0;
  9.         next[1] = 0;
  10.         while (i < T[0])
  11.         {
  12.                 if (0 == j || T[i] == T[j])
  13.                 {
  14.                         i++;
  15.                         j++;
  16.                         if (T[i] == T[j])
  17.                         {
  18.                                 next[i] = next[j];
  19.                         }
  20.                         else
  21.                         {
  22.                                 next[i] = j;
  23.                         }
  24.                 }
  25.                 else
  26.                 {
  27.                         j = next[j];
  28.                 }

  29.         }
  30. }

  31. void GetString(char str[])
  32. {
  33.         int i;
  34.         char temp;
  35.         scanf_s("%c", &temp);
  36.         for (i = 1; temp != ' '&&temp != '\n'; i++)
  37.         {
  38.                 str[i] = temp;
  39.                 scanf_s("%c", &temp);
  40.         }
  41.         str[0] = i - 1 ;
  42. }

  43. int KMP(char S[], char T[],int next[])
  44. {
  45.         int i=1,j=1;
  46.         int flag = 0;
  47.         while (i <= S[0] )
  48.         {
  49.                 if (j==0||S[i] == T[j])
  50.                 {
  51.                         i++;
  52.                         j++;
  53.                 }
  54.                 else
  55.                 {
  56.                         j = next[j];
  57.                 }
  58.                 if (j > T[0] )
  59.                 {
  60.                         flag = 1;
  61.                         break;
  62.                 }
  63.         }
  64.         if (flag)return i;
  65.         else return 0;
  66. }


  67. int main()
  68. {
  69.         char S[256], T[256] ;
  70.         int next[256];

  71.         cout << "输入主串:";
  72.         GetString(S);
  73.         cout << "输入子串:";
  74.         GetString(T);

  75.         GetNext(T, next);

  76.         int pos = KMP(S, T, next)-T[0];

  77.         if (pos)cout << "YES,in the no." << pos << endl;
  78.         else cout << "NO"<< endl;

  79.         system("PAUSE");
  80. }
复制代码

评分

参与人数 2鱼币 +8 收起 理由
hjcwsad + 5
小甲鱼 + 3

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 07:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表