博客

字符串匹配(1): 朴素字符串匹配的实现及复杂度分析

  • Post author:
  • Post category:IT
  • Post comments:0评论

(这篇文章在tumblr上显示不正常，因为tumblr自动对backslash做了转义。如果你发现这篇文章中的数学公式无法正常显示，请点击https://www.sunchangming.com/blog/post/4622.html )

问题描述：

在字符串t中寻找字符串p第一次出现的位置

实现：

C语言版本：

//Find the first occurrence of find in s.
char *strstr(const char *t, const char *p) {
  char c, sc;
  size_t len;

  if ((c = *find++) != '\0') {
    len = strlen(p);
    do {
      do {
        if ((sc = *t++) == '\0') return (NULL);
      } while (sc != c);
    } while (strncmp(t, p, len) != 0);
    s--;
  }
  return ((char *)t);
}

C++版本：

（下面这段代码仅仅是为了做算法分析而写的demo，不要在实际项目中使用它，因为它效率很差。）

#include <string>
#include <iostream>

std::string::size_type find(const std::string &t, const std::string &p) {
  if (t.length() < p.length()) return std::string::npos;
  std::string::size_type end = t.length() - p.length();
  for (std::string::size_type i = 0; i <= end; ++i) {
    bool mismatch = false;
    for (std::string::size_type j = 0; j != p.length(); ++j) {
      if (t[i + j] != p[j]) {
        mismatch = true;
        break;
      }
    }
    if (!mismatch) {
      return i;
    }
  }
  return std::string::npos;
}

int main(int argc, char *argv[]) {
  if (argc < 3) return -1;
  std::string str = argv[1];
  std::string str2 = argv[2];
  std::cout << find(str, str2) << std::endl;
  return 0;
}

算法复杂度分析

下面以需要进行多少次单个字符的比较为衡量标准，分析这种算法的复杂度。

下面假设待匹配的字符串为t，长度为n。模式字符串为p，长度为m。

最坏情况(Worst-Case)

假设t是“aaaaaaaaaaaa”这样，p是”aaaab”，那么匹配一定失败。所以外层循环需要执行n-m+1次。而内层循环也需要执行m次。所以总计为O((n-m+1)m)。

平均情况(Average-Case)

假设每个字符有d种取值可能性，比如对于纯小写字母组成的字符串，d=26。并且假设每种字符出现的概率都相等，皆为1/d。

那么随机选取2个字符，它们相等的概率为1/d。

那么随机选取2个长度为2的字符串，它们相等的概率为\frac{1}{d^2}。

那么随机选取2个长度为3的字符串，它们相等的概率为\frac{1}{d^3}。

…

首先分析一下内层循环需要执行多少次比较。

 for (std::string::size_type j = 0; j != p.length(); ++j) {
      if (t[i + j] != p[j]) {
        mismatch = true;
        break;
      }
    }

假设需要比较c次(c>=2)，那么说明t和p的前c-1个字符都相同，即t[i+k]=p[k] (k=0…c-2)。

如果我们把所需比较的次数看成一个随机变量X，那么

有$$ \begin{equation} P\{X=c\}= \begin{cases} 1- \frac{1}{d} & c=1 \ \frac{1}{d^{c-1}}(1-\frac{1}{d}) & c=2 \dots {m-1} \ \frac{1}{d^{m-1}} & c=m \end{cases} \end{equation} $$

即

$$ \begin{equation} P\{X=c\}= \begin{cases} \frac{1}{d^{c-1}}(1-\frac{1}{d}) & c=1 \dots {m-1} \ \frac{1}{d^{m-1}} & c=m \end{cases} \end{equation} $$

然后求随机变量X的数学期望，

$$ \begin{array}{lcl} E(X)=\sum_{i=1}^{m-1}{\frac{i}{d^{i-1}}(1-\frac{1}{d})} + \frac{m}{d^{m-1}} \ = \sum_{i=1}^{m-1}{\frac{i}{d^{i-1}}} - \sum_{i=1}^{m-1}{\frac{i}{d^i}} + \frac{m}{d^{m-1}} \ = 1 + \sum_{i=1}^{m-2}{\frac{i+1}{d^i}} - \sum_{i=1}^{m-2}{\frac{i}{d^i}} - \frac{m-1}{d^{m-1}} + \frac{m}{d^{m-1}} \ = 1 + \sum_{i=1}^{m-2}{\frac{1}{d^i}}+ \frac{1}{d^{m-1}} \ = 1 + \frac{1}{d} + \frac{1}{d^2} \dots + \frac{1}{d^{m-1}} \ = \frac{1-d^{-m}}{1-d^{-1}} \end{array} $$

我没有想到化简后最终的结果竟然这么简单，就是一个等比数列而已。并且它的取值范围很狭窄（与m关系不大）

$$ 1 \leq E(X) < 1+ \frac{2}{d} < 2 $$

然后把外层循环也考虑进去，所以总的复杂度为O(n-m+1)。

这就是为什么简单的算法在实际中依然很有效。

This article is from:https://www.sunchangming.com/blog/post/4622.html

发表回复