1.实现strstr

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2

示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1

说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

 int n=s.size(),m=p.size();
       if ((m==0))
       {
        return 0;
       }
       //设置哨兵
       s.insert(s.begin(),' ');
       m.insert(s.begin(),' ');
       //预处理 前缀表
       //i 后缀末尾
       //j 前缀末尾
       for(int i=2; j=0;i<=m;i++)
       {
        while(j&&p[i]!=p[j+1])j==next[j]//回退
        if(p[i]==p[j+1])j++;
        next[i]=j;
       }
       //匹配过程
       for(int i=1;j=0;i<=m;i++)
       {
        while(j&& s[i]!=p[j+1])j=next[j];
        if(s[i]==p[j+1])j++;
        if(j==m)return i-m;
       }
}

关于kmp参考

2.重复的字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

void getNext (int* next, const string& s){
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++){
            while(j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if(s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern (string s) {
        if (s.size() == 0) {
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
}

这里在给出一个数推导，就容易理解很多。

假设字符串s使用多个重复子串构成（这个子串是最小重复单位），重复出现的子字符串长度是x，所以s是由n * x组成。

因为字符串s的最长相同前后缀的的长度一定是不包含s本身，所以最长相同前后缀长度必然是m * x，而且 n – m = 1，（减去首尾）

所以如果 nx % (n – m)x = 0，就可以判定有重复出现的子字符串。

next 数组记录的就是最长相同前后缀字符串：KMP算法精讲 (opens new window)这里介绍了什么是前缀，什么是后缀，什么又是最长相同前后缀)，如果 next[len – 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。

最长相等前后缀的长度为：next[len – 1] + 1。(这里的next数组是以统一减一的方式计算的，因此需要+1，两种计算next数组的具体区别看这里：字符串：KMP算法精讲 (opens new window))

数组长度为：len。

如果len % (len – (next[len – 1] + 1)) == 0 ，则说明数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除，说明该字符串有重复的子字符串。

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/129650.html