Leetcode-- string

KMP Algorithm ： Solve string matching problems

Prefix ： A substring containing the first letter but not the last letter  

Text string ：aabaabaaf 

Pattern string ：aabaaf

Find the Longest Prefix suffix :

a  0    aa  1 aab 0 aaba 1 aabaa 2 aabaaf 0

The prefix table is 010120

next Array （ In case of conflict, you should go back ）：-1 0 -1 0 1 -1

next[0] = 0 Represents a string with only one character , The maximum length of the same pre suffix is 0

344 Reverse string

void reverseString(vector<char>& s) {
        for(int i = 0, j = s.size()-1; i < s.size()/2; i++,j--){
            swap(s[i],s[j]);
        }
    }

541   every other 2k Before character inversion k Characters

 string reverseStr(string s, int k) {
        for(int i = 0; i < s.size();i = i + (2 * k)){
            //1. every other 2k Characters before k Character inversion 
            //2. The remaining characters are greater than k  Less than 2k  Before the k A reversal 
            if(i + k <= s.size()){
                reverse(s.begin()+i,s.begin()+i+k);
                continue;
            }
            //3. The remaining characters are less than k individual , Invert all remaining characters 
            reverse(s.begin()+i,s.end());
        }
        return s;
    }

58  Left rotation string

string reverseLeftWords(string s, int n) {
        /*
         Local inversion + Global inversion   Achieve the purpose of left rotation 
        1. Reverse the interval [0,n-1]
        2. Reverse the interval [n,end]
        3. Invert the entire string 
        */
        reverse(s.begin(),s.begin() + n);
        reverse(s.begin()+n,s.end());
        reverse(s.begin(),s.end());
        return s;
    }

5 Replace blank space

string replaceSpace(string s){
    // Count the number of spaces 
    int count = 0;
    int sOldSize = s.size();
    for(int i = 0; i < sOldSize;i++){
        if(s[i] == ' ')
            count++;
    }
    // Extended string s Size 
    s.resize(sOldSize + count * 2);
    int sNewSize = s.size();
    // Replace spaces from back to front 
    for(int i = sNewSize - 1,j = sOldSize - 1 ; j < i ; i--,j--){
        if(s[j] != ' '){
            s[i] = s[j];
        }else{
            s[i] = '0';
            s[i-1] = '2';
            s[i-2] = '%';
            i -= 2;
        }
    }
    return s;
}

151 Invert the words in the string

original : abc_def    After reversing ：  def_abc

First reverse each word cba_fed ; Inverting the entire string def_abc   

28  Realization strStr

kmp Algorithm

void getNext(int* next,string& s){
        int j = 0;//j  Is the end of the prefix 
        next[0] = 0;
        for(int i = 1; i < s.size(); i++){ //i Is the end of the suffix 
            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) {
        if(needle.size() == 0) return 0;
        int next[needle.size()];
        getNext(next,needle); //next The values in the array represent the prefix such as longest appearance 
        int j = 0;
        for(int i = 0; i < haystack.size(); i++){
            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);  // 3 - 2 + 1
            }
        }            
        return -1;
    }

459 Repeated substrings

void getNext (int* next, const string& s){
        next[0] = 0;
        int j = 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;
        }
    }
 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] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }