回顾串的朴素模式匹配

╰半夏微凉° 2022-12-24 00:50 147阅读 0赞

## 一 概述 ##

**关于串的朴素模式匹配中我们应该先了解主串，子串，模式串之间的关系：**

主串：任何一个字符串都可以作为主串如：S = 'HelloWorld'。

子串：一般理解为某个主串的子串，如主串S的字串可以有：'Hello'，'World'。由此可以发现子串一定是某主串中存在的连续字符串才叫做子串。

模式串：模式串只要满足串的概念即可，同时模式串匹配是希望在某一指定的主串中找到该串，但不要求一定存在。

## 二 串的模式匹配 ##

串的模式匹配是指在主串中找到与模式串相同的子串，并返回其所在位置。

在串的模式匹配过程中我们需要进行定位操作：若主串S中存在于串T值相同的子串，则返回它在主串S中第一次出现的位置，否者函数值为0。

## 三 通过串的基本操作实现串的朴素模式匹配 ##

**操作步骤：**

1. 确定一个主串和一个模式串。

2. 将模式串与主串进行对比，如果第一个字符相同则比较后续字符。

3. 如果后续字符都相同则直接返回首字符的位置。

4. 如果后续字符中存在不同的字符，则将模式串整体往后移一位，然后重复1的步骤。

5. 继续进行2的判断，若满足则返回结束，如不满足则继续步骤3。

**串的朴素模式匹配中串的基本操作实例**

//静态数组定义串，静态数组实现定长顺序存储，当有关静态数组实现的代码执行成功后，其所占的空间会自动被回收。
    typedef  struct{
        char ch[MAXLEN]; //每个分量存储一个字符串。
        int length;  //串的实际长度。
    }SString;
    
    //求子串,用Sub返回串S的第pos个字符起长度为len的子串
    bool SubString(SString *Sub,SString S, int pos, int len){
    
        //子串范围越界
        if(pos+len-1 > S.length){
            return false;
        }
    
        for(int i = pos; i < pos + len; i++){
            Sub->ch[i-pos+1] = S.ch[i];
            Sub->length = len;
        }
        return true;
    }
    
    //子串与主串的比较操作。若S>T,则返回值 > 0; 若S = T, 则返回值 = 0； 若S < T, 则返回值 < 0
    int StrCompare(SString S,SString T) {
        for (int i = 1; i <= S.length && i <= T.length; i++) {
            if(S.ch[i] != T.ch[i]) {
                return S.ch[i] - T.ch[i];
            }
        }
        //扫描过的所有字符都相同，则长度长的串更大
        return S.length - T.length;
    }
    
    //定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置，否则函数值为0.
    int Index(SString S, SString T) {
        int i = 1, n = S.length, m = T.length;
        SString *sub;
        while(i <= n-m+1) {
            SubString(sub,S,i,m);
            if(StrCompare(*sub,T) != 0) ++i;
            else return i; //返回子串在主串的位置
        }
        return 0;   //S中不存在与T相同的子串
    }

## 四 模式匹配算法的性能分析 ##

当主串长度为M，而模式串的长度为m

最好时间复杂度：匹配成功时最好情况的时间复杂度为O(m)。匹配失败时最好的时间复杂度为O(M-m+1)。

由于很多实际的应用场景中，主串要比模式串长的多，即M>>m。所以O(M-m+1) ≈ O(M)。

最坏时间复杂度：因为直到匹配成功/匹配失败最多需要(M-m+1)\*m次比较，同上因为在很多的实际应用场景中，主串要比模式串长的多，即M>>m，所以此时的时间复杂度为O(Mm)。