Chinaunix首页 | 论坛 | 博客
  • 博客访问: 43190
  • 博文数量: 37
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 410
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
  • 认证徽章:
个人简介

90后空巢老码农

文章分类

全部博文(37)

文章存档

2018年(36)

2017年(1)

我的朋友

分类: C/C++

2018-04-29 14:14:19

说到字符串匹配,脑袋里自然而然的冒出来KMP,哎,当年还是专门找了好久的材料,最终算是懂点皮毛,在这里跟大家分享一下。
最初的字符串匹配算法都是从头开始,逐个匹配过去,奈何效率不高,最后就是那些“懒”而聪明的大神们,想出了这个算法,供人们使用,在这里先定义一下参与字符串匹配的两个参数:模式字符串,以及目标字符串;我们可以理解为在目标字符串中找出模式字符串~~~
KMP算法就是充分利用模式串的自身信息求出一个巨有用的数组next来进行后续的匹配工作。计算next数组代码如下:

点击(此处)折叠或打开

  1.     int patternLen = patternStr.size();
  2.     int targetLen = targetStr.size();
  3.     //next数组一定要记得开大一点
  4.     int next[10005] = { -1 };
  5.     //计算next数组。 ps: next 数组含义--当前位置i失配时, 模式串的指针应该回溯到的位置即next[i]
  6.     //j表示前缀,i表示后缀
  7.     int j = -1, i = 0;
  8.     next[0] = -1;
  9.     while (i < patternLen)
  10.     {
  11.         if (j == -1 || patternStr[i] == patternStr[j])
  12.         {

  13.             i++;
  14.             j++;
  15.             next[i] = j;
  16.         }
  17.         else
  18.         {
  19.             j = next[j];
  20.         }
  21.     }
之后匹配模式串和目标字符串的过程和上面的代码比较类似,如下:

点击(此处)折叠或打开

  1. //在目标串中寻找模式串的个数, i表示 目标串的下标,j表示模式串的下标
  2. i = j = 0;
  3. int count = 0;
  4. while (i < targetLen)
  5. {
  6.     if (j == -1)
  7.     {
  8.         i++;
  9.         j++;
  10.     }
  11.     if (patternStr[j] == targetStr[i])
  12.     {
  13.         //当完全匹配时,计数+1,但是为了找下一个完全匹配串,假设最后一个没有匹配,进入下一次循环
  14.         if (j == (patternLen - 1))
  15.         {
  16.             count++;
  17.             j = next[j];
  18.         }
  19.         else
  20.         {
  21.             j++;
  22.             i++;
  23.         }
  24.     }
  25.     else
  26.     {
  27.         j = next[j];
  28.     }
  29. }
下面是全部代码:

点击(此处)折叠或打开

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;

  4. int main()
  5. {
  6.     string targetStr;
  7.     string patternStr;
  8.     int N;
  9.     cin >> N;
  10.     int n = 0;
  11.     while (n < N)
  12.     {
  13.         cin >> patternStr >> targetStr;
  14.         int patternLen = patternStr.size();
  15.         int targetLen = targetStr.size();
  16.         //next数组一定要记得开大一点,老子可是调了好几天的,可恶的边界条件。。。。
  17.         int next[10005] = { -1 };
  18.         //计算next数组。 ps: next 数组含义--当前位置i失配时, 模式串的指针应该回溯到的位置即next[i]
  19.         //j表示前缀,i表示后缀
  20.         int j = -1, i = 0;
  21.         next[0] = -1;
  22.         while (i < patternLen)
  23.         {
  24.             if (j == -1 || patternStr[i] == patternStr[j])
  25.             {

  26.                 i++;
  27.                 j++;
  28.                 next[i] = j;
  29.             }
  30.             else
  31.             {
  32.                 j = next[j];
  33.             }
  34.         }
  35.         /*
  36.         for (int t = 0; t < patternLen; t++)
  37.         cout << next[t] << " ";
  38.         cout << endl;
  39.         */
  40.         //在目标串中寻找模式串的个数, i表示 目标串的下标,j表示模式串的下标
  41.         i = j = 0;
  42.         int count = 0;
  43.         while (i < targetLen)
  44.         {
  45.             if (j == -1)
  46.             {
  47.                 i++;
  48.                 j++;
  49.             }
  50.             if (patternStr[j] == targetStr[i])
  51.             {
  52.                 //当完全匹配时,计数+1,为了找下一个完全匹配串,假设没有匹配,进入下一次循环
  53.                 if (j == (patternLen - 1))
  54.                 {
  55.                     count++;
  56.                     j = next[j];
  57.                 }
  58.                 else
  59.                 {
  60.                     j++;
  61.                     i++;
  62.                 }
  63.             }
  64.             else
  65.             {
  66.                 j = next[j];
  67.             }
  68.         }
  69.         cout << count << endl;
  70.         n++;
  71.     }
  72.     return 0;
  73. }
欢迎大家提出宝贵意见~~~
阅读(30) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册