锐客网

  1. 首页 > it技术 > >

leetcode 28.实现strStr()--KMP算法--字符串匹配

leetcode

leetcode 28.实现strStr()--KMP算法--字符串匹配
文章图片

1.暴力 遍历

class Solution { public: int strStr(string haystack, string needle) { if(needle.empty()) return 0; if(haystack.empty()) return -1; if(haystack.size()

【leetcode 28.实现strStr()--KMP算法--字符串匹配】 leetcode 28.实现strStr()--KMP算法--字符串匹配
文章图片


2.KMP算法：字符串匹配
leetcode 28.实现strStr()--KMP算法--字符串匹配
文章图片

next数组可以理解为状态的跳转：
（1）状态i左侧的字符全部匹配成功，当状态i右侧第一个字符匹配不成功时，跳转到状态next[i]。
（2）因为状态i左侧串的子串与状态next[i]左侧串相同（即：状态i左侧串的长度为next[i]的前缀子串和后缀子串相同）
//求解next数组 int i=0,j=-1; vector next(needle.size()+1); next[0]=-1; while(i

next[0]=-1是为了字符串匹配时的计算方便。
字符串匹配时的情况：
（1）text[i]与pattern[0]匹配不成功，则下一个比较text[i+1]与pattern[0]；
（2）j>0，text[i]与pattern[j]匹配不成功，则下一个比较text[i]与pattern[next[j]]；
（3）j>0，text[i]与pattern[j]匹配成功，则下一个比较text[i+1]与pattern[j+1]；

完整代码：
class Solution { public: int strStr(string haystack, string needle) { if(needle.empty()) return 0; if(haystack.empty()) return -1; if(haystack.size() next(needle.size()+1); next[0]=-1; while(i

leetcode 28.实现strStr()--KMP算法--字符串匹配
文章图片

    推荐阅读


    上一篇：编写两个进程a和b，利用共享内存技术，a向共享内存写字符串，b将从共享内存中读到的字符串在屏幕上打印出来。

    下一篇：python菱形