【五十三】【算法分析与设计】1392. 最长快乐前缀，686. 重复叠加字符串匹配，796. 旋转字符串，KMP算法

1392. 最长快乐前缀

思路

过程

686. 重复叠加字符串匹配

796. 旋转字符串

string内置函数find

KMP算法

结尾

1392. 最长快乐前缀

「快乐前缀」 是在原字符串中既是非空前缀也是后缀（不包括原字符串自身）的字符串。

给你一个字符串 s，请你返回它的 最长快乐前缀。如果不存在满足题意的前缀，则返回一个空字符串 "" 。

示例 1：

输入：s = "level" 输出："l" 解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）和 4 个后缀（"l", "el", "vel", "evel"）。最长的既是前缀也是后缀的字符串是 "l" 。

示例 2：

输入：s = "ababab" 输出："abab" 解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。

提示：

1 <= s.length <= 10(5)

s 只含有小写英文字母

思路

这道题目的意思是，给我们一个字符串s，需要我们返回这个字符串s的最长公共前后缀的长度。

计算某一个字符串s的最长公共前后缀的长度，依靠kmp算法中计算match模式串next数组的计算方式即可。

首先创建一个next数组，next[i]表示0~i-1区间的最长公共前后缀长度。

因此next数组的长度应该为s.size()+1，因为我们需要得到0~s.size()-1区间的最长公共前后缀长度。

对应是next[s.size()],所以next的大小选哟是s.size()+1。

过程

1. if (next.size() == 1) return ""; kmp计算next数组，一定不要忘记next数组长度为1的时候直接返回。

因为next数组中，next[0]=-1,next[1]=0，这两个位置是人为定义的，因此为了不能越界访问，当next长度为1的时候，直接返回。

2. next[0] = -1, next[1] = 0; int i = 2; int cn = 0;

初始化，从i=2位置开始填写next数组。对于每一个新的i，cn一定是next[i-1]的值。

3. while (i < next.size()) { if (s[cn] == s[i - 1]) { next[i] = cn + 1; i++, cn = cn + 1;

while循环，黑盒，内部逻辑将i位置的next计算完毕。

如果s[cn]==s[i-1]，此时next[i]=cn+1。

填写好next[i]，维护下一个i和cn的值。

i++，cn=cn+1。

5. } else if (cn != 0) { cn = next[cn];

如果s[cn]!=s[i-1]，此时cn=next[cn]，继续判断s[cn]与s[i-1]。

6. } else { next[i] = 0; i++, cn = 0;

如果cn==0，对应的next[cn]=-1,此时next[i]=0。

维护下一个i和cn。

i++，cn=0。 7. return s.substr(0, next[s.size()]); 返回next[s.size()],表示0~s.size()区间长度的最长公共前后缀。

class Solution {
public:
    string longestPrefix(string s) {
        vector<int> next(s.size() + 1);
        if (next.size() == 1)
            return "";

        next[0] = -1, next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < next.size()) {
            if (s[cn] == s[i - 1]) {
                next[i] = cn + 1;
                i++, cn = cn + 1;
            } else if (cn != 0) {
                cn = next[cn];
            } else {
                next[i] = 0;
                i++, cn = 0;
            }
        }
        return s.substr(0, next[s.size()]);
    }
};

686. 重复叠加字符串匹配

给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。

示例 1：

输入：a = "abcd", b = "cdabcdab" 输出：3 解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。

示例 2：

输入：a = "a", b = "aa" 输出：2

示例 3：

输入：a = "a", b = "a" 输出：1

示例 4：

输入：a = "abc", b = "wxyz" 输出：-1

提示：

1 <= a.length <= 10(4)

1 <= b.length <= 10(4)

a 和 b 由小写英文字母组成

首先让a不断进行叠加操作，语句是a+=a。

直到a的长度an>=原先a的长度+bn。

因为重复叠加a字符串，b如果是a的子串，开始匹配的位置一定是原先a字符串中某一个字符。

因此可以确定叠加字符串的上界。

如何计算花费了多少个a字符串叠加？

综上所述，a的叠加数等于(len-1)/an+2=(bn-cd-1)/an+2=(bn-(an-(x-y))-1)/an+2=(bn-an+(x-y)-1)/an+2。

利用KMP算法计算a叠加串中b子串开始位置。

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int maxlen = a.size() + b.size();
        int an = a.size();
        int bn = b.size();
        while (a.size() < maxlen)
            a += a;

        vector<int> next = getNext(b);
        int x = 0, y = 0;
        while (x < a.size() && y < b.size()) {
            if (a[x] == b[y]) {
                x++, y++;
            } else if (y != 0) {
                y = next[y];
            } else {
                x++;
            }
        }

        if (an - (x - y) >= bn) {
            return 1;
        }
        if (y == b.size()) {
            return (bn + x - y - an - 1) / an + 2;
        } else {
            return -1;
        }
    }

    vector<int> getNext(string match) {
        vector<int> next(match.size());
        if (match.size() == 1)
            return {-1};
        next[0] = -1, next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < next.size()) {
            if (match[cn] == match[i - 1]) {
                next[i] = cn + 1;
                i++;
                cn = cn + 1;
            } else if (cn != 0) {
                cn = next[cn];
            } else {
                next[i] = 0;
                i++;
                cn = 0;
            }
        }
        return next;
    }
};

796. 旋转字符串

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。

s 的 旋转操作 就是将 s 最左边的字符移动到最右边。

例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea' 。

示例 1:

输入: s = "abcde", goal = "cdeab" 输出: true

示例 2:

输入: s = "abcde", goal = "abced" 输出: false

提示:

1 <= s.length, goal.length <= 100

s 和 goal 由小写英文字母组成

string内置函数find

两个a字符串叠加在一起，叠加后的字符串寻找模式串goal，看是否能在叠加后的字符串子串找到模式串。

利用string内置函数find寻找子串开始匹配位置。

class Solution {
public:
    bool rotateString(string s, string goal) {
        if(s.size()!=goal.size()) return false;
        s+=s;
        int pos=s.find(goal);
        if(pos==-1) return false;
        else return true;
    }
};

KMP算法

class Solution {
public:
    bool rotateString(string s, string goal) {
        if(s.size()!=goal.size()) return false;
        s+=s;
        vector<int> next=getNext(goal);
        int x=0,y=0;
        while(x<s.size()&&y<goal.size()){
            if(s[x]==goal[y]){
                x++,y++;
            }else if(y!=0){
                y=next[y];
            }else{
                x++;
            }
        }

        if(y==goal.size()) return true;
        else return false;
    }

    vector<int> getNext(string match){
        if(match.size()==1) return {-1};
        vector<int> next(match.size());
        next[0]=-1;
        next[1]=0;
        int i=2;
        int cn=0;
        while(i<next.size()){
            if(match[cn]==match[i-1]){
                next[i]=cn+1;
                i++,cn=cn+1;
            }else if(cn!=0){
                cn=next[cn];
                
            }else{
                next[i]=0;
                i++,cn=0;
            }
        }

        return next;
    }
};