Skip to content

字符串.md

Latest commit

 

History

History
323 lines (303 loc) · 10.3 KB

字符串.md

File metadata and controls

323 lines (303 loc) · 10.3 KB

字符串理论基础

  • 字符串是若干字符组成的有限序列，也可以理解为是一个字符数组

数组中常见的面试题型

  1. 暴力枚举
  2. 双指针算法（见双指针算法总结）
  3. KMP算法

字符串题型

剑指offer.05 替换空格

class Solution {
public:
    string replaceSpace(string s) {
        string res;
        for (auto c: s){
            if (c == ' '){
                res += "%20";
            }
            else res += c;
        }
        return res;
    }
};

leetcode.58 最后一个单词的长度

  • 链接https://leetcode.cn/problems/length-of-last-word/
  • 解题方法：
    创建一个临时字符串，和一个答案数组（用来存所有单词）
    遍历原字符串，如果遍历到空格，判断临时字符串是否为空
    如果临时字符串非空则说明已经遍历完一个单词，将其加入答案数组中并清空临时字符串
    如果遍历到的不是空格，将其加入临时字符串中
    最后在答案数组中找到最后一个单词输出其长度
  • leetcode解题代码
class Solution {
public:
    int lengthOfLastWord(string s) {
        s += " ";// 在字符串末尾加上一个空格防止遗漏最后一个单词
        string temp;
        vector<string> res;
        for (auto c: s){
            if (c == ' '){
                if (!temp.empty()){
                    res.push_back(temp);
                    temp.clear();
                }
            }
            else temp += c;
        }
        if (res.empty()) return 0;
        return res.back().size();
    }
};

剑指offer.58 左旋转字符串

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.end());
        reverse(s.begin(), s.end() - n);
        reverse(s.end() - n, s.end());
        return s;
    }
};

KMP算法

应用场景

  • $KMP$算法一般用于字符串匹配问题
  • 例如：给出两个字串 $S$，$P$，需要判断 $P$ 串是否为 $S$ 串的子串

前缀和后缀

  • 前缀：包含第一个字符不包含最后一个字符（从左往右）
  • 后缀：包含最后一个字符不包含最后一个字符（从左往右）
  • 例如：$a$
    $a$ 既是第一个字符也是最后一个字符，所以不存在前缀和后缀
  • 例如：$aa$ 前缀为：$a$ 后缀为：$a$
  • 例如：$aab$ 前缀为：$a$, $aa$ 后缀为：$b$, $ab$

前缀表

前缀表存的是最长相等前后缀的长度
例如：$aabaaf$

前缀 后缀 最长相等前后缀的长度
$a$ 空 空 $0$
$aa$ $a$ $a$ $1$
$aab$ $a, aa$ $b, ab$ $0$
$aaba$ $a, aa, aab$ $a, ba, aba$ $1$
$aabaa$ $a, aa, aab, aaba$ $a, aa, baa, abaa$ $2$
$aabaaf$ $a, aa, aab, aaba, aabaa$ $f, af, aaf, baaf, abaaf$ $0$
  • 在 $KMP$ 算法当中，用一个 $next$ 数组存的就是以当前字符结尾的最长相等前后缀
    例如：$aabaaf$
    $a: 0, aa: 1, aab: 0, aaba: 1, aabaa: 2$
    $next = [0, 1, 0, 1, 2]$

前缀表在KMP算法中的作用

  • 暴力解法中，我们需要两重循环遍历 $P$ 串和 $S$ 串，直到找到匹配的字串，时间复杂度为 $O(n*m)$，$n$，$m$ 分别表示 $P$ 串和 $S$ 串的长度
  • $KMP$ 算法的核心思想就是用前缀表记录已经匹配过的文本内容，使得当发生匹配冲突的时候，可以不需要重新遍历，而是通过前缀表回退到之前匹配成功过的位置继续匹配

next数组的实现（前缀表实现）

  • 构造 $next$ 数组分为四步：
  1. 初始化
    定义两个指针 $i，j$
    $i$ 指向后缀末尾位置，$j$ 指向前缀末尾位置
    例如**$aabaaf$**
    从 $a$ 开始的时候不存在前缀也不存在后缀，见上表第一行
    所以 $next$ 数组初始化为 $0$，$j$ 从 $0$ 开始，$i$ 从 $1$ 开始
  2. 处理前后缀不相同的情况（冲突的情况）
    $P$ 串 aabaaf
    $S$ 串 aabaabaaf
    当发生匹配冲突时（字符 $f$ 和 $b$ 不匹配），$j$ 指针在 $P$ 串字符 $f$ 的位置，$i$ 指针在 $S$ 串字符 $b$ 的位置，$j$ 应该回退到字符 $b$ 的位置也就是 $next[j-1]$ 的位置继续匹配
  3. 处理前后缀相同的情况
    前后缀相同时，$i$, $j$ 都向后移动一位（$i$ 在for循环中向后移动）
  4. 更新 $next$ 数组
    将 $next$ 数组更新为 $j$
  • 代码模板
void getNext(vector<int> next, string s) {
        next[0] = 0;
        for(int i = 1, j = 0; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
                j = next[j - 1]; 
            }
            if (s[i] == s[j]) {
                j ++;
            }
            next[i] = j;
        }
    }

KMP算法题型

Acwing.831 KMP字符串

给定一个字符串 $S$，以及一个模式串 $P$，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 $P$ 在字符串 $S$ 中多次作为子串出现。

求出模式串 $P$ 在字符串 $S$ 中所有出现的位置的起始下标。

输入格式
第一行输入整数 $N$，表示字符串 $P$ 的长度。

第二行输入字符串 $P$。

第三行输入整数 $M$，表示字符串 $S$ 的长度。

第四行输入字符串 $S$。

输出格式
共一行，输出所有出现位置的起始下标（下标从 $0$ 开始计数），整数之间用空格隔开。

数据范围
$1 \leq N \leq 10^{5}$
$1 \leq M \leq 10^{6}$

输入样例：

3  
aba  
5
ababa

输出样例：

0 2
  • 解题代码
#include <iostream>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
char p[N], s[M];
int ne[N];


int main(){
    cin >> n >> p >> m >> s;
    // kmp模板
    ne[0] = 0;
    for (int i = 1, j = 0; i < n; i ++){
        while (j > 0 && p[i] != p[j])
            j = ne[j - 1];
        if (p[i] == p[j])
            j ++;
        ne[i] = j;
    }
    // 两个字符串匹配
    for (int i = 0, j = 0; i < m; i ++){
        while (j > 0 && s[i] != p[j]){
            j = ne[j - 1];
        }
        if (s[i] == p[j])
            j ++;
        if (j == n) 
            cout << i - n + 1 << ' ';
    }
    
    return 0;
    
}

leetcode.28 找出字符串中第一个匹配项的下标

class Solution {
public:
    int strStr(string s, string p) {
        int n = p.size(), m = s.size();
        vector<int> next(n);
        // kmp模板
        next[0] = 0;
        for (int i = 1, j = 0; i < n; i ++){
            while (j > 0 && p[i] != p[j])
                j = next[j - 1];
            if (p[i] == p[j])
                j ++;
            next[i] = j;
        }
        // 两个字符串匹配
        for (int i = 0, j = 0; i < m; i ++){
            while (j > 0 && s[i] != p[j])
                j = next[j - 1];
            if (s[i] == p[j])
                j ++;
            if (j == n)
                return i - n + 1;
        }
        return -1;
    }
};

leetcode.459 重复的子字符串

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> next(n);
        // kmp模板
        next[0] = 0;
        for (int i = 1, j = 0; i < n; i ++){
            while (j > 0 && s[i] != s[j])
                j = next[j - 1];
            if (s[i] == s[j])
                j ++;
            next[i] = j;
        }
        // 周期
        int t = n - next[n - 1];
        return t < n && n % t == 0;
    }
};

leetcode.796 旋转字符串

class Solution {
public:
    bool rotateString(string s, string p) {
        if (s.size() != p.size()) return false;
        int n = p.size();
        // kmp模板
        vector<int> next(n);
        next[0] = 0;
        for (int i = 1, j = 0; i < n; i ++){
            while (j > 0 && p[i] != p[j])
                j = next[j - 1];
            if (p[i] == p[j])
                j ++;
            next[i] = j;
        }
        // s+s包括了若干次旋转的可能
        // 字符匹配
        s += s;
        for (int i = 0, j = 0; i < n + n; i ++){
            while (j > 0 && s[i] != p[j])
                j = next[j - 1];
            if (s[i] == p[j])
                j ++;
            if (j == n) return true;
        }
        return false;
    }
};