字符串.md

01基础知识

#include <string>
int main(){
 string s;//可以之后再赋值
 s="hello";
 cout<<s[1];//支持下标访问
 
 }![image](https://github.com/Housenbao/LeetcodeHome/assets/45709425/2eb052d4-8cd8-49ee-8198-3ab16db8ef17)

image

02KMP算法

KMP算法是字符串模式匹配的算法，其核心思想是利用最长相同前后缀来缓解指针回退的问题。 例如aabaaf这个字符串如果与aabaabaaf配对，那么当匹配到i->b,j->f的时候，b!=f因此子串的指针要回退，回退到j=0显然是多余的，因为aabaa是一个特殊的字符串，它的前缀和后缀都是相同的那么最佳的回退位置就是aa后面一个。用一个next数组把每个的最佳回退位置记录下来，减少匹配时候的时间复杂度，这就是KMP算法。 而获得Next数组的方法也很巧妙，和KMP匹配算法是类似的，是利用模式串与模式串进行KMP。 代码：

class Solution {
public:
    void getNext(int* next,string &s){
        int j = 0;
        next[0] = 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;
        }

    }
    int strStr(string haystack, string needle) {
        int i=0,j=0;
        int next[needle.size()];
        getNext(next,needle);
        for(int i =0;i<haystack.size();i++){
            //当不相等的时候就子串指针往前退，退到什么位置呢？如果j前面的从0到j-1的子串是一个前后缀相同的串，
            while(j>0&&haystack[i]!=needle[j]){
                j=next[j-1];
            }
            if(haystack[i]==needle[j]){
                j++;
            }
            if(j==needle.size()){
                return (i - needle.size() + 1);
            }
            
        }
        return -1;



    }
};