Problem6767--【学习系列】—— 字符串 —— 3. 字符串匹配

6767: 【学习系列】—— 字符串 —— 3. 字符串匹配

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 0Submit Num: 0StatisticsShowOff!

Description

字符串匹配问题

简介

又称模式匹配（pattern matching）。该问题可以概括为「给定字符串 $S$ 和 $T$，在主串 $S$ 中寻找子串 $T$」。字符 $T$ 称为模式串 (pattern)。

类型

  • 单串匹配：给定一个模式串和一个待匹配串，找出前者在后者中的所有位置。
  • 多串匹配：给定多个模式串和一个待匹配串，找出这些模式串在后者中的所有位置。
    • 出现多个待匹配串时，将它们直接连起来便可作为一个待匹配串处理。
    • 可以直接当做单串匹配，但是效率不够高。
  • 其他类型：例如匹配一个串的任意后缀，匹配多个串的任意后缀……

暴力做法

简称 BF (Brute Force) 算法。该算法的基本思想是从主串 $S$ 的第一个字符开始和模式串 $T$ 的第一个字符进行比较，若相等，则继续比较二者的后续字符；否则，模式串 $T$ 回退到第一个字符，重新和主串 $S$ 的第二个字符进行比较。如此往复，直到 $S$ 或 $T$ 中所有字符比较完毕。
如果用暴力匹配的思路，并假设现在文本串 $S$ 匹配到 $i$ 位置，模式串 $P$ 匹配到 $j$ 位置，则有：
  • 如果当前字符匹配成功（即 S[i] == P[j]），则 i++，j++，继续匹配下一个字符；
  • 如果失配（即 S[i]! = P[j]），令 i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为 0。
 理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：

参考代码 

int ViolentMatch(char* s, char* p)  
{  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
  
    int i = 0;  
    int j = 0;  
    while (i < sLen && j < pLen)  
    {  
        if (s[i] == p[j])  
        {  
            //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++      
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0      
            i = i - j + 1;  
            j = 0;  
        }  
    }  
    //匹配成功，返回模式串p在文本串s中的位置，否则返回-1  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

时间复杂度

设 $n$ 为主串的长度，$m$ 为模式串的长度。默认 $m \ll n$。
在最好情况下，BF 算法匹配成功时，时间复杂度为 $O(n)$；匹配失败时，时间复杂度为 $O(m)$。
在最坏情况下，每趟不成功的匹配都发生在模式串的最后一个字符，BF 算法要执行 $m(n-m+1)$ 次比较，时间复杂度为 $O(nm)$。
如果模式串有至少两个不同的字符，则 BF 算法的平均时间复杂度为 $O(n)$。但是在 OI 题目中，给出的字符串一般都不是纯随机的。

 举个例子，如果给定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，现在要拿模式串P去跟文本串S匹配，整个过程如下所示：
    1. S[0] 为 B，P[0] 为 A，不匹配，执行第②条指令：“如果失配（即 S[i]! = P[j]），令 i = i - (j - 1)，j = 0”，S[1] 跟 P[0] 匹配，相当于模式串要往右移动一位（i=1，j=0）

 2. S[1] 跟 P[0] 还是不匹配，继续执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[2]跟P[0]匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i = i - (j - 1)，j = 0”，i从2变到4，j一直为0）

3. 直到 S[4] 跟 P[0] 匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，可得S[i]为S[5]，P[j]为P[1]，即接下来S[5]跟P[1]匹配（i=5，j=1）

4. S[5] 跟 P[1] 匹配成功，继续执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此进行下去


5. 直到 S[10] 为空格字符，P[6] 为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相当于S[5]跟P[0]匹配（i=5，j=0）

6. 至此，我们可以看到，如果按照暴力匹配算法的思路，尽管之前文本串和模式串已经分别匹配到了 S[9]、P[5]，但因为 S[10] 跟 P[6] 不匹配，所以文本串回溯到 S[5]，模式串回溯到 P[0]，从而让 S[5] 跟 P[0] 匹配。

而 S[5] 肯定跟 P[0] 失配。为什么呢？因为在之前第 4 步匹配中，我们已经得知 S[5] = P[1] = B，而 P[0] = A，即 P[1] != P[0]，故 S[5] 必定不等于 P[0]，所以回溯过去必然会导致失配。
那有没有一种算法，让 $i$ 不往回退，只需要移动 $j$ 即可呢？

Source/Category

 
Submit