【数据结构与算法分析】0基础带你学数据结构与算法分析05--串 (string)

简介: 笔记

前言


串是一种特殊的线性结构,它的内部元素只存储字符,因此又称为字符串。其特殊性主要来源于我们对字符序列的依赖程度很高,而特化一个线性结构并为其增加一些针对于字符的常用算法,可以方便我们的使用,提高编码效率。


在大部分的实现中,string 都有一个标志结尾的字符 \0 ,其 ASCII 值为 0,因此在遇到 \0 时就认为这个字符串结束。但是有一些实现使用单独的变量来标记,因此这种字符串中即使存在 \0 也可能并不是串的结尾。因此串的长度为真实的长度减一 (因为 \0 将占用一个位置)。长度为 0 的字符串被称为空串,一般使用 ∅\varnothing∅ 表示,其中只有一个 \0 。


串的匹配


在一个串中寻找指定子串是一个最常用的算法,解决方法也有多种。我们将指定的串称之为匹配串,并假设原串长度为 m,匹配串长度为 n。


朴素算法

从下标为 0 开始比较原串与匹配串,若不相同,则移位到下标为 1,直到找完原串的所有子字符串。这个算法很简单,也很好理解,其时间复杂度为 O(mn) 。


int strstr(const string& source, const string& pattern) {
  int m = source.size(), n = pattern.size();
  for (int i = 0; i + n <= m; i++) {
    bool flag = true;
    for (int j = 0; j < n; j++) {
      if (source[i + j] != pattern[j]) {
        flag = false;
        break;
      }
    }
    if (flag) {
      return i;
    }
  }
  return -1;
}


KMP 算法

KMP 实际上是三位计算机科学家的名字缩写,Knuth、Morris 和 Pratt,有意思的是,之后你还会见到 Morris 的名字,而 Pratt 的博士生导师就是 Knuth。


Knuth 1938 年生,1977 年访问中国时姚期智的夫人储枫为其取的中文名高德纳。老爷子的成就实在太多了, 计算机程序设计艺术、TeX、 METAFONT、文学式编程、LR解析理论 等等,还获得过冯诺伊曼奖与图灵奖。而老爷子是个十分有趣的人,TeX 的版本号趋近于 π 而 METAFONT 的版本号趋近于 e;为了他的著作他还开了家银行,为在他的著作中找的任何错误的人奖励 2.56 美元 (256 pennies is one hexadecimal dollar),并对每个有价值的建议提供 0.32 美元的奖金。如今他还在十二月份安排了讲座。如果你想了解老爷子可以访问他的 个人主页。


KMP 的主要思想是:一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置。此算法利用这一特性以避免重新检查先前匹配的字符,因此 KMP 的核心算法即求解本身包含的信息。这一信息被称为前缀函数,记作 π(i) 。对于区间 [0:i](0≤i<n) ,π(i) 是最长的一对相等的真前缀与真后缀的长度,如果没有符合条件的真前缀/真后缀则 π(i)=0 。真前缀、真后缀即与串本身不相等的前缀 / 后缀子串。


假设有匹配串 aabaab ,则有前缀函数


π(0)=0 ,串 s[0:0]s[0:0]s[0:0] 没有真前缀

π(1)=1 ,一对最长相等真前缀、真后缀为 s[0] 和 s[1] ,长度为 1

π(2)=0 ,串 s[0:2]s[0:2]s[0:2] 没有相等的真前缀与真后缀

π(3)=1 ,一对最长相等真前缀、真后缀为 s[0] 和 s[3] ,长度为 1

π(4)=2 ,一对最长相等真前缀、真后缀为 s[0:1] 和 s[3:4] ,长度为 2

π(5)=0 ,一对最长相等真前缀、真后缀为 s[0:2] 和 s[3:5] ,长度为 3

接下来就是 KMP 如何使用前缀函数,前缀函数代表了当前如果匹配失败了,在 已匹配的串 中,有多少真后缀是与真前缀相同的,那么在接下来的匹配中我们可以直接忽略这些相同的真前缀 / 真后缀,从而接着匹配字符串,跳过这些不必要的匹配。

1.png

前缀函数的实现

观察前缀函数,我们可以观察到:


如果 s[i]=s[π(i−1)] ,那么 π(i)=π(i−1)+1
如果 s[i]≠s[π(i−1)] ,那么需要递归地向前寻找
当满足 s[i]=s[j],j=π(π(π(… ))−1) 时, π(i)=π(j)+1
当全部不满足时,则 π(i)=0
void get_prefix_array(const string& pattern, const int len, int pi[]) {
  pi[0] = 0;
  for (int i = 1, j = 0; i < len; i++) {
    while (j > 0 && pattern[i] != pattern[j]) {
      j = pi[j - 1];
    }
    j += pattern[i] == pattern[j];
    pi[i] = j;
  }
}

KMP 的实现

我们需要利用先生成前缀数组,再对原串进行遍历匹配模式串,因此总的时间复杂度需要 O(m+n)。


int strstr(const string& source, const string& pattern) {
  int n = source.size(), m = pattern.size();
  int pi[m];
  get_prefix_array(pattern, n, pi);
  for (int i = 0, j = 0; i < n; i++) {
    while (j > 0 && source[i] != pattern[j]) {
      j = pi[j - 1];
    }
    if (source[i] == pattern[j]) {
      j++;
    }
    if (j == m) {
      return i - m + 1;
    }
  }
  return -1;
}


Sunday 算法

Sunday 算法是 BM 算法的变种,与


KMP 的核心思路一样,利用 pattern 已给出的信息,最大程度的跳过不匹配的字符。


Sunday 的思想较为简单,处理一个 pattern 偏移表,该表主要映射了 pattern 串中存在的每个字符到末尾的距离,如果有多个相同字符,则用更靠近末尾的映射替换之前的值。 Sunday 算法如果发现无法匹配,则观察这个坏字符的下一个位置的字符 c 来决定步进的长度:


如果 c 不存在于 pattern 中,直接将 pattern 的起始位置与 c 的下一个字符对齐

如果 c 存在于 pattern 中,则将最靠近末尾的该字符与 c 对齐

// 为实现的简便,假设 source 中只包含 ASCII 字符
int strstr(const string& source, const string& pattern) {
  int n = source.size(), m = pattern.size();
  int shift[128] = {0};
  for (int i = 0; i < m; i++) {
    shift[pattern[i]] = m - i;
  }
  for (int i = 0, end = n - m + 1; i < end;) {
    int j = 0;
    while (source[i + j] == pattern[j]) {
      ++j;
      if (j == m) {
        return i;
      }
    }
    i += shift[source[i + m]] == 0 ? m + 1 : shift[source[i + m]];
  }
  return -1;
}
相关文章
|
8天前
|
机器学习/深度学习 算法 存储
[数据结构]——算法的时间复杂度和空间复杂度
[数据结构]——算法的时间复杂度和空间复杂度
|
15天前
|
存储 监控 NoSQL
Redis处理大量数据主要依赖于其内存存储结构、高效的数据结构和算法,以及一系列的优化策略
【5月更文挑战第15天】Redis处理大量数据依赖内存存储、高效数据结构和优化策略。选择合适的数据结构、利用批量操作减少网络开销、控制批量大小、使用Redis Cluster进行分布式存储、优化内存使用及监控调优是关键。通过这些方法,Redis能有效处理大量数据并保持高性能。
38 0
|
1天前
|
算法
重拾数据结构和算法——脑图
重拾数据结构和算法——脑图
3 0
|
6天前
|
算法 搜索推荐 Java
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
7 0
|
7天前
|
存储 搜索推荐 算法
C语言数据结构算法,常用10种排序实战
插入排序(Insertion Sort) 希尔排序(Shell Sort) 选择排序(Selection Sort) 冒泡排序(Bubble Sort) 归并排序(Merge Sort) 快速排序(Quick Sort) 堆排序(Heap Sort) 基数排序(Radix Sort)
9 1
C语言数据结构算法,常用10种排序实战
|
13天前
|
缓存 算法 Java
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
|
15天前
|
机器学习/深度学习 算法 数据可视化
Python 数据结构和算法实用指南(四)(4)
Python 数据结构和算法实用指南(四)
27 1
|
15天前
|
机器学习/深度学习 存储 算法
Python 数据结构和算法实用指南(四)(3)
Python 数据结构和算法实用指南(四)
16 1
|
15天前
|
存储 算法 搜索推荐
Python 数据结构和算法实用指南(四)(2)
Python 数据结构和算法实用指南(四)
12 0
|
15天前
|
存储 算法 Serverless
Python 数据结构和算法实用指南(四)(1)
Python 数据结构和算法实用指南(四)
17 0