C语言 字符串匹配

#include <stdio.h>

  

const char key[][12] = { "happy", "new", "year", "2014" }

 

// 是否完全匹配某一个特定的 key 

int match1(const char *s, const char *t)

{

  while (*s && *t && *s++ == *t++)

  return !(*s || *t)

}

  

// 是否匹配一组 key 的中一个 

int match(const char *s)

{

  int i, j

  for (i = 0 i < sizeof key / sizeof key[0] i++)

    if (match1(s, key[i]))

    {

      // 如果匹配到某个 key，则打印匹配到的 key 

      for (j = 0 key[i][j] j++)  putchar(key[i][j])

      putchar('\n')

      return 1

    }

  return 0

}

  

int main()

{

  char s[BUFSIZ]

  int i, k

 

  // 输入一个字符串

  for (i = 0 i < BUFSIZ && (s[i] = getchar()) != '\n' i++)

  s[i] = '\0'

  match(s)

  return 0

}

以上程序是判断输入的字符串是否是某个 key 中的一个。

如果不要求完全匹配，而是要求检测输入的字符串是否含有某个 key，则程序如下：

#include <stdio.h>

  

const char key[][12] = { "happy", "new", "year", "2014" }

 

// 是否含有某一个特定的 key 

int match1(const char *s, const char *t)

{

  const char *p, *q, *r

  for (p = s, q = t *p && *q p = r, q = t)

  {

    for (r = p + 1 *p == *q p++, q++)

    if (*q == '\0') return 1

    if (*p == '\0') return 0

  }

  return 0

}

  

// 是否含有一组 key 的中一个 

int match(const char *s)

{

  int i, j

  for (i = 0 i < sizeof key / sizeof key[0] i++)

    if (match1(s, key[i]))

    {

      // 如果匹配到某个 key，则打印匹配到的 key 

      for (j = 0 key[i][j] j++)  putchar(key[i][j])

      putchar('\n')

      return 1

    }

  return 0

}

  

int main()

{

  char s[BUFSIZ]

  int i, k

 

  // 输入一个字符串

  for (i = 0 i < BUFSIZ && (s[i] = getchar()) != '\n' i++)

  s[i] = '\0'

 

  if (match(s))

  {

    // 如果匹配到某个 key，则打印输入的原始字符串 

    for (k = 0 k < i k++) putchar(s[k])

    putchar('\n')

  }

  return 0

}

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法：

主串和模式串：

在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m

我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

BF 算法的时间复杂度是 O(n*m)

等价于

比如匹配Google 和Goo 是最好时间复杂度，匹配Google 和ble是匹配失败的最好时间复杂度。

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特—莫里斯—普拉特算法。KMP算法主要分为两个步骤：字符串的自我匹配，目标串和模式串之间的匹配。

看来网上很多的文章，感觉很多的都没有说清楚，这里直接复制阮一峰的内容，讲的很清晰

内容来自 http://www.ruanyifeng.com/blog/

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

因为B与A不匹配，搜索词再往后移。

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

接着比较字符串和搜索词的下一个字符，还是相同。

直到字符串有一个字符，与搜索词对应的字符不相同为止。

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

因为 6 - 2 等于4，所以将搜索词向后移动4位。

因为空格与C不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

因为空格与A不匹配，继续后移一位。

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP 算法的 3 到 4 倍。

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）

未完待续

参考文章：

字符串匹配的Boyer-Moore算法

1、定义一个正则表达式，用来测试字符串is的匹配。

2、接着，使用定义的正则表达式，测试单词this的匹配结果。

3、运行程序，可以看到匹配的结果为true，即以上定义的正则表达式不能实现严格的匹配。

4、如果要实现正则表达式严格的匹配，则要在表达式中加入\b符号。

5、运行程序，可以看到结果为false，即正则表达式严格匹配字符串了。

---