字符串类算法笔记

1.KMP算法笔记

以下为2篇kmp详解链接

https://leetcode-cn.com/leetbook/read/array-and-string/cpoo6/

https://blog.csdn.net/qq_45806146/article/details/104911112?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&utm_relevant_index=2

#include <iostream>
#include "string"
#include "vector"
using namespace std;
class Solution {
public:
    vector<int> next;
    //KMP的核心难点 构造next串
    void buildNext(string s) {
        int m = s.size(), j = 0;
        int t = -1;
        next.resize(m);
        // 因为第一个字母没有前缀，所以next[0] = -1
        next[0] = t;
        while (j < m - 1) {
            // t < 0 也就是 t == -1,要从模式串的第一位开始匹配，然后主串也要向后移一下
            if (t < 0 || s[j] == s[t]) {
                j++;
                t++;
                next[j] = t;
            } else {
                t = next[t];
            }
        }

    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) return 0;
        buildNext(needle);
        // 指向主串
        int n = haystack.size(), i = 0;
        // 指向模式串
        int m = needle.size(), j = 0;
        while (i < n && j < m) {
            // j < 0 说明 j==-1要从头开始匹配了
            if (j < 0 || haystack[i] == needle[j]) {
                i++;
                j++;
            } else {
                //如果j<0说明两个串需要从头开始匹配 主串位置往前增1 模式串从0开始
                // haystack[i] 和 needle[j]不匹配，要从模式串下标为next[j]的继续匹配，也就是最长公共前缀后缀的长度
                j = next[j];
            }
        }
        // 如果j == m证明模式串匹配完毕，在主串中找到了模式串，范围模式串在主串中出现的第一个下标，i - j
        if (j == m) {
            return i - j;
        }
        return -1;
    }
};

2.寻找旋转排序数组中的最小值

二分查找

int findMin(vector<int>& nums) {
        int high = nums.size()-1;
        int low = 0;
        int mid;
        while (low<high)
        {
            mid = (low+high)/2;
            if(nums[mid]<nums[high]){
                high = mid;
            }else{
                low = mid + 1;
            }
        }
        return nums[low];     
    }