首页 计算机科学 算法 LeetCode

# 右旋字符串

题目链接🔗

不申请额外空间，只在本串操作。

  • 右旋：将字符串后面 n 个字符右移到前面。这样字符串分成了两个部分。
  • 右移 n 位，就是将第二段放在前面，第一段放在后面，先不考虑里面字符的顺序，整体倒叙就行了。
  • 此时第一段和第二段顺序符合结果，但里面字符顺序被倒序，更正回来。

右旋字符串

// 版本一
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    int len = s.size(); // 获取长度
    reverse(s.begin(), s.end()); // 整体反转
    reverse(s.begin(), s.begin() + n); // 先反转前一段，长度 n
    reverse(s.begin() + n, s.end()); // 再反转后一段
    cout << s << endl;
    return 0;
}

# 实现 Strstr ()

题目链接🔗

KMP 经典题目。KMP 的经典思想：当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

# 什么是前缀表

前缀表是用来回退的，它记录了模式串与主串 (文本串) 不匹配的时候，模式串应该从哪里开始重新匹配。

此时就要问了前缀表是如何记录的呢？

首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

那么什么是前缀表：记录下标 i 之前（包括 i）的字符串中，有多大长度的相同前缀后缀。

# 最长公共前后缀

文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

前缀表要求的是相同前后缀的长度。

因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。

模式串与前缀表对应位置的数字表示的就是：下标 i 之前（包括 i）的字符串中，有多大长度的相同前缀后缀。

再来看一下如何利用 前缀表找到当字符不匹配的时候应该指针应该移动的位置。如动画所示：

找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。

为什么要前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀。

所以要看前一位的 前缀表的数值。

前一个字符的前缀表的数值是 2， 所以把下标移动到下标 2 的位置继续比配。

最后就在文本串中找到了和模式串匹配的子串了。

# 构建 next 数组

以前缀表统一减一之后的 next 数组来做演示。

next数组匹配

构建 next 数组就是计算模式串 s 的前缀表过程：

  1. 初始化

    定义两个指针，j 指向前缀末尾，i 指向后缀末尾。

    next[i] 表示 i（包括 i）之前最长相等的前后缀长度（其实就是 j）

  2. 处理前后缀不同的情况

    遍历模式串 s 的循环下标 i 要从 1 开始。

    因为 j 初始化为 - 1，所以 s[i] 与 s[j+1] 的比较。

    怎么回退呢？

    next[j] 就是记录着 j（包括 j）之前的子串的相同前后缀的长度。

    那么 s[i] 与 s[j+1] 不相同，就要找 j+1 前一个元素在 next 数组里的值（就是 next[j] ）。

  3. 处理前后缀相同的情况

    如果 s[i] == s[j + 1] ，那么就同时向后移动 i 和 j 说明找到了相同的前后缀，同时还要将 j（前缀的长度）赋给 next[i] , 因为 next[i] 要记录相同前后缀的长度。

void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意 i 从 1 开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将 j（前缀的长度）赋给 next [i]
    }
}

代码构建 next 数组的逻辑流程动画如下：

构建next

# 使用 next 数组匹配

在文本串 s 中找出是否出现过模式串 t。

定义两个下标 i, j，分别指向文本串和模式串的起始位置。

j 初始值依然为 - 1，因为 next 数组里记录的起始位置为 - 1。

i 从 0 开始遍历文本串。

如果 s[i] != t[j+1] ,j 就要从 next 数组里寻找下一个匹配的位置。

如果 s[i] == t[j + 1] ，那么 i 和 j 同时向后移动。

如何判断在文本串 s 里出现了模式串 t 呢，如果 j 指向了模式串 t 的末尾，那么就说明模式串 t 完全匹配文本串 s 里的某个子串了。

本题要在文本串字符串中找出模式串出现的第一个位置 (从 0 开始)，所以返回当前在文本串匹配模式串的位置 i 减去 模式串的长度，就是文本串字符串中出现模式串的第一个位置。

使用 next 数组匹配的代码如下：

int j = -1; // 因为 next 数组里记录的起始位置为 - 1
for (int i = 0; i < s.size(); i++) { // 注意 i 就从 0 开始
    while(j >= 0 && s[i] != t[j + 1]) { // 不匹配
        j = next[j]; //j 寻找之前匹配的位置
    }
    if (s[i] == t[j + 1]) { // 匹配，j 和 i 同时向后移动
        j++; //i 的增加在 for 循环里
    }
    if (j == (t.size() - 1) ) { // 文本串 s 里出现了模式串 t
        return (i - t.size() + 1);
    }
}

题目整体代码如下：

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = -1;
        next[0] = j;
        for(int i = 1; i < s.size(); i++) { // 注意 i 从 1 开始
            while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
                j = next[j]; // 向前回退
            }
            if (s[i] == s[j + 1]) { // 找到相同的前后缀
                j++;
            }
            next[i] = j; // 将 j（前缀的长度）赋给 next [i]
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = -1; //// 因为 next 数组里记录的起始位置为 - 1
        for (int i = 0; i < haystack.size(); i++) { // 注意 i 就从 0 开始
            while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
                j = next[j]; //j 寻找之前匹配的位置
            }
            if (haystack[i] == needle[j + 1]) { // 匹配，j 和 i 同时向后移动
                j++; //i 的增加在 for 循环里
            }
            if (j == (needle.size() - 1) ) { // 文本串 s 里出现了模式串 t
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

# 重复的子字符串

题目链接🔗

# 移动匹配

当一个字符串 s：abcabc，内部由重复的子串组成，那么这个字符串的结构一定是由前后相同的子串组成。

那么既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前面的子串做后串，就一定还能组成一个 s，如图：

所以判断字符串 s 是否由重复子串组成，只要两个 s 拼接在一起，里面还出现一个 s 的话，就说明是由重复子串组成。

当然，我们在判断 s + s 拼接的字符串里是否出现一个 s 的的时候，要刨除 s + s 的首字符和尾字符，这样避免在 s+s 中搜索出原来的 s，我们要搜索的是中间拼接出来的 s。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
        if (t.find(s) != std::string::npos) return true;
        return false;
    }
};

# KMP

在一个串中查找是否出现过另一个串，这是 KMP 的看家本领。

在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串。

# 推理

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

因为字符串 s 的最长相同前后缀的长度一定是不包含 s 本身，所以 最长相同前后缀长度必然是m∗xm * x，而且n−m=1n - m = 1。

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

如果next[len−1]!=−1next[len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。

最长相等前后缀的长度为：next[len−1]+1next[len - 1] + 1。(这里的 next 数组是以统一减一的方式计算的，因此需要 +)

数组长度为： len 。

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

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

class Solution {
public:
    void getNext (int* next, const string& s){
        next[0] = -1;
        int j = -1;
        for(int i = 1;i < s.size(); i++){
            while(j >= 0 && s[i] != s[j + 1]) {
                j = next[j];
            }
            if(s[i] == s[j + 1]) {
                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] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
            return true;
        }
        return false;
    }
};