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

问题描述:

在字符串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{align} 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{align} $$

$$ \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)。

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

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥