python算法与数据结构：03字符串_数据结构字符串测试03

字符串

字符串匹配算法：

字符串匹配：

字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置。
如下面两个字符串：

char *str = "bacbababadababacambabacaddababacasdsd";
char *ptr = "ababaca";
1
2

str有两处包含ptr
分别在str的下标10，26处包含ptr。

1.朴素算法：

一般匹配字符串时，我们从目标字符串str（假设长度为n）的第一个下标选取和ptr长度（长度为m）一样的子字符串进行比较，如果一样，就返回开始处的下标值，不一样，选取str下一个下标，同样选取长度为n的字符串进行比较，直到str的末尾（实际比较时，下标移动到n-m）。这样的时间复杂度是O(n*m)。

> def n_matching(t, p):  # 朴素的串匹配算法的实现(p是要匹配的字符串，t是被匹配的字符串
>     j, i = 0, 0  # i，j的初始化
>     n, m = len(t), len(p)  # m，n分别是t，p字符串的长度
>     while j < n and i < m:  # i，j指针在被扫描的字符串内
>         if t[j] == p[i]:  # 如果两字符串中某个字符相等
>             j, i = j+1, i+1  # 指针后移一位，为比较下一位字符做准备
>         else:
>             j, i = j-i+1, 0  # 不匹配时，指针分别后移
>     if i == m:  # 匹配成功的情况
>         return j-i  # 返回被匹配字符串的匹配位置的首字符的位置
>     return -1  # 不匹配返回异常值
 
1
2
3
4
5
6
7
8
9
10
11
12

2.BM算法：

BM算法定义了两个规则：

• 坏字符规则：当文本串中的某个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外，如果"坏字符"不包含在模式串之中，则最右出现位置为-1。

• 好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。

下面举例说明BM算法。例如，给定文本串“HERE IS A SIMPLE EXAMPLE”，和模式串“EXAMPLE”，现要查找模式串是否在文本串中，如果存在，返回模式串在文本串中的位置。

1. 首先，“文本串"与"模式串"头部对齐，从尾部开始比较。”S“与”E“不匹配。这时，”S“就被称为"坏字符”（bad character），即不匹配的字符，它对应着模式串的第6位。且"S“不包含在模式串”EXAMPLE“之中（相当于最右出现位置是-1），这意味着可以把模式串后移6-(-1)=7位，从而直接移到”S"的后一位。
   

2. 依然从尾部开始比较，发现"P“与”E“不匹配，所以”P“是"坏字符”。但是，"P“包含在模式串”EXAMPLE"之中。因为“P”这个“坏字符”对应着模式串的第6位（从0开始编号），且在模式串中的最右出现位置为4，所以，将模式串后移6-4=2位，两个"P"对齐。
   

3. 依次比较，得到 “MPLE”匹配，称为"好后缀"（good suffix），即所有尾部匹配的字符串。注意，“MPLE”、“PLE”、“LE”、"E"都是好后缀。
   

4. 发现“I”与“A”不匹配：“I”是坏字符。如果是根据坏字符规则，此时模式串应该后移2-(-1)=3位。问题是，有没有更优的移法？
   

5. 更优的移法是利用好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串中上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。所有的“好后缀”（MPLE、PLE、LE、E）之中，只有“E”在“EXAMPLE”的头部出现，所以后移6-0=6位。可以看出，“坏字符规则”只能移3位，“好后缀规则”可以移6位。每次后移这两个规则之中的较大值。这两个规则的移动位数，只与模式串有关，与原文本串无关。

6. 继续从尾部开始比较，“P”与“E”不匹配，因此“P”是“坏字符”，根据“坏字符规则”，后移 6 - 4 = 2位。因为是最后一位就失配，尚未获得好后缀。
   

时间复杂度：

BM算法从模式串的尾部开始匹配，且拥有在最坏情况下 O(N) 的时间复杂度。有数据表明，在实践中，比 KMP 算法的实际效能高，可以快大概 3-5 倍 。

最好的情况是O（n/m）

3.KMP算法：

前缀：除最后一个字符外，字符串的所有头部子串

后缀：除第一个字符外，字符串的所有尾部字串

部分匹配值：字符串前缀和后缀最长相等前后缀的长度

next数组的算法：

KMP算法的过程：

KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的，那么，它是则呢样来消除回溯的呢？就是因为它提取并运用了加速匹配的信息。加速信息，即数组 next 的提取是整个 KMP 算法中最核心的部分，

朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：

时间复杂度：

朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高

一般匹配字符串时，我们从目标字符串str（假设长度为n）的第一个下标选取和ptr长度（长度为m）一样的子字符串进行比较，如果一样，就返回开始处的下标值，不一样，选取str下一个下标，同样选取长度为n的字符串进行比较，直到str的末尾（实际比较时，下标移动到n-m）。这样的时间复杂度是O(n*m)。

参考:
1.https://blog.csdn.net/starstar1992/article/details/54913261

2.[https://blog.csdn.net/DBC_121/article/details/105569440?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159049780119726869039056%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=159049780119726869039056&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_allfirst_rank_v2~rank_v25-7-105569440.first_rank_v2_rank_v25&utm_term=bm%E7%AE%97%E6%B3%95+]