- 👋 Hi, I’m @Beast Cheng
- 👀 I’m interested in photography, hiking, landscape…
- 🌱 I’m currently learning python, javascript, kotlin…
- 📫 How to reach me --> 458290771@qq.com
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑💻
此外，《程序员必备技能》专栏日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏
引言
主串：“红红火火恍恍惚惚红红火火笑出猪叫哈哈哈哈哈哈哈试试哦沙发”
主串中斜体的笑出猪叫就是与模式串匹配的子串
模式串：“笑出猪叫”
模式串：“笑出狗叫”
字符串模式匹配：在主串中找到与模式相同的子串，并返回其所在位置
子串：主串的一部分，一定存在
模式串：不一定能在主串中找到
思想
主串长度为 n ，模式串长度为 m
将主串中所有长度为 m 的子串依次与模式串对比，知道找到一个完全匹配的子串，或所有的子串都不匹配为止
最多对比 n − m + 1 n-m+1 n−m+1 个子串
事实上，这个过程和上一节中的 Index(S, T) 定位操作一样[[4.1.2 串的存储结构#Index(S, T) 定位]]
接下来，尝试不使用字符串的基本操作，直接通过数组下标实现朴素模式匹配算法
若当前子串匹配失败，则主串指针 i 指向下一个子串的第一个位置，模式串指针 j 回到模式串的第一个位置
i = i - j + 2;
j = 1;
若 j > T.length ，则当前子串匹配成功，返回当前子串第一个字符的位置—— i - T.length
具体代码实现：
int Index(SString S, SString T){
int i = 1, j = 1;
while(i <= S.length && j <= T.length){
if(S.ch[i] == T.ch[i]){
++i;++j; // 继续比较后面的字符
}else{
i = i-j+2;
j = 1; // 指针后退开始重新匹配
}
}
if(j > T.length)
return i-T.length;
else
return 0;
}
最坏时间复杂度 = O ( n m ) O(nm) O(nm)
最坏的情况，每个子串都要对比 m 个字符，共 n − m + 1 n-m+1 n−m+1 个子串
复杂度 = O ( ( n − m + 1 ) m ) = O ( n m ) （很多时候， n ≫ m ，所以可以把 m 2 给去掉） =O((n-m+1)m) = O(nm)\,\,\,\,（很多时候，n \gg m，所以可以把 m^2给去掉） =O((n−m+1)m)=O(nm)（很多时候，n≫m，所以可以把m2给去掉）