当前位置：首页 > news >正文

4.2_1朴素模式匹配算法

news 2025/6/27 19:37:09

知识总览：

什么是字符串的模式匹配：

主串：想从该串获取结果的串

模式串：想搜索的内容，不一定在主串中能搜到，子串一定能在主串中搜到

字符串模式匹配：在主串找模式串并返回找到的第一个模式串所在位置

朴素模式匹配算法：

暴力匹配，从主串选取跟模式串长度一样的子串去跟模式串对比，俩串相等返回首字符下标，俩串不相等继续找，直到找到为止返回首字符下标或者找完也找不到为止。

实现方法1：Index()函数定位操作

跟上一节找主串的子串函数一样

注意目前的串都是用的静态数组且是数组第一个字符位置不适用的形式，即数组存储字符的下标跟字符位序相同，且找模式串可寻找的次数为n-m+1(n为主串，m为模式串)

实现方法2：不用Index()函数定位，使用指针

第一轮：

设置2个扫描指针，分别扫描主串和模式串，指针指到哪则2个串的字符比较到哪，开始i和j分别指向主串S和模式串T的下标为1的第一个字符，分别为a和a即相等，则俩指针后移指向下标为2的第2个字符，都为b继续后移，来指针都指向第3个字符a都相等，继续后移指向第4个字符a相等，继续后移指向第5个字符都为b相等，继续后移此时俩指针都指向第6个字符，i指向主串S的a，j指向模式串的T的c，则俩字符不相等，指向主串的指针i回到指向下一个子串的第一个位置，即主串S的第2个字符位置，指向模式串的指针j回到模式串的第一个位置

i=i-j+2；//即此时i=6,j=6，下一轮i=i-j+2=2

//俩指向字符不相等时，j当前的值表示匹配到了子串的第几个字符，i-j就可以让i的值回到目前这个子串的前边一个位置，i和j都是统一往前移的，因为指针i要指向下一个子串的第一个位置，所以要在此基础上+2，如下图现在j指向了当前子串的第6个字符,i=6,j=6,i=i-j=0即i回到了这个子串的前边一个位置(注意是当前子串的前边一个位置，不是当前子串的第一个位置，这意味着要指向下一个子串的第一个位置要+2，因为+1就又指向当前子串的第一个位置了)，然后还要刨除这个子串的第一个位置指向下一个字串的第一个位置，则要i=i+2=2

j=1；//即此时j=6,下一轮j=1，j指向模式串起始位置

第2轮：

i的值恢复为2即i==2，j的值恢复为1即j==1，俩指针指向的值为b和a不相等，即i指向的当前子串和模式串不相等，则i=i-j=2-1=1即i回到当前子串b的前一个位置，i=i+2=3为指向下一个子串的第一个位置，指向模式串T的指针j回到模式串第一个位置即j==1

i=i-j+2；//即此时i=2,j=1，下一轮i=i-j+2=2-1+2=3

j=1；//即此时j=6,下一轮j=1，j指向模式串起始位置

第3轮：

上同，i从第3个字符开始的子串和j=1开始的模式串比较，每当发现i和j所指的字符相同的时候，让i和j分别+1，当i==4，j==2时不相等，i回到下一个子串的第一个位置，j回到起始位置

i=i-j+2；//即此时i=4,j=2，下一轮i=i-j+2=4-2+2=4

j=1；//即此时j=2,下一轮j=1，j指向模式串起始位置

第4轮：

每当发现i和j所指的字符相同的时候，让i和j分别+1，当j所指的位置超出了模式串的长度，就说明匹配成功，则返回当前子串的第一个字符位置即让i-j即可，注意没有+1，因为在匹配成功的时候i和j都已经往前移动了1个位置，所以当i-j的时候其实指向的位置为当前子串的第一个字符位置

代码版：

2个指针i和j，i指向主串，j指向模式串，初始值都为1即指向主串和模式串的第一个字符，如下while循环

if(S.ch[i]==T.ch[j]); ++i;++j；即当前2个指针指向的字符相等，让i和j都+1

i=i-j+2;j=1；即当前2个指针指向的字符不相等则让i回到下一个子串的第一个字符位置，j回到模式串第1个位置

return i-T.length；如果匹配成功，则说明j>T.length，已跳出while循环

return 0;；即匹配失败，即i已经把整个主串走了一遍，即在走到主串的最后一个字符时，不相等，i的下一轮下标为S.length+1（我怎么感觉S.length要比实际的字符个数多1个，因为S数组中存储的第一个位置没有存元素啊，比说最后一个字符index=3,实际S.length=4吧，那下一个位置i不就是4吗，那这个while循环不是还能走一遍吗，但是走的话if第一个语句就数组下标越界了吧。。。。。。。。。。。。。。。。）