数据结构笔记——朴素模式匹配算法

亦凉 2023-03-14 08:11 15阅读 0赞

**目录**

一、什么是模式匹配

二、朴素模式匹配算法

三、朴素模式匹配算法性能分析

四、总结

--------------------

## **一、什么是模式匹配** ##

主串：S=‘wangdao’

子串：'wang'、'ang'、'ao'....

模式串：'gda'、'bao'

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

## **二、朴素模式匹配算法** ##

定位操作（模式匹配）——Index(S,T)。

若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置：否则函数值为0

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]

**代码实现：**

int Index(SString S,SString T){
        int k = 1;
        int i = k, j = 1;
        while(i <= S.length && j <= T.length){
            if(S.ch[i] == T.ch[j]){
                ++i;
                ++j;
            }else{
                k++;
                i = k;
                j = 1;
            }
        }
        if(j > T.length)
            return k;
        else
            return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1][]

## **三、朴素模式匹配算法性能分析** ##

**1.较好的情况：每个子串第一个字符都与模式串不匹配**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2][]

**2.最好的情况：一一匹配**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3][]

**3.最坏的情况：子串和模式串最后一个字符不匹配**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4][]

若模式串长度为m，主串长度为n，则直到匹配成功/匹配失败最多需要(n-m+1)\*m次比较

最坏时间复杂度O(nm)

## **四、总结** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: /images/20230312/e5437bda01e44356a55c908883800c21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1]: /images/20230312/9c64e3f9c066466f941dee4a20a153fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2]: /images/20230312/852dd9d6a2764ad7b059394d60f56e23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3]: /images/20230312/ff27b873a8794797b6dfef28966cf508.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4]: /images/20230312/f1bdc114d6b045798b392066ff276988.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5]: /images/20230312/5fdb4d88eb844f8faaf4da84d402d5ec.png