leetcode--字符串

KMP算法：解决字符串匹配问题

前缀：包含首字母不包含尾字母的子串 

文本串：aabaabaaf 

模式串：aabaaf

求最长相等前后缀:

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

前缀表是 010120

next数组 （遇到冲突以后要回退）：-1 0 -1 0 1 -1

next[0] = 0 表示当只有一个字符的字符串，相同前后缀的最大长度是0

344 反转字符串

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  每隔2k个字符反转前k个字符

 string reverseStr(string s, int k) {
        for(int i = 0; i < s.size();i = i + (2 * k)){
            //1.每隔2k个字符将前k个字符反转
            //2.剩余字符大于k 小于2k 将前k个反转
            if(i + k <= s.size()){
                reverse(s.begin()+i,s.begin()+i+k);
                continue;
            }
            //3.剩余字符少于k个，将剩余字符全部反转
            reverse(s.begin()+i,s.end());
        }
        return s;
    }

58 左旋转字符串

string reverseLeftWords(string s, int n) {
        /*
        局部反转+整体反转 达到左旋转的目的
        1.反转区间[0,n-1]
        2.反转区间[n,end]
        3.反转整个字符串
        */
        reverse(s.begin(),s.begin() + n);
        reverse(s.begin()+n,s.end());
        reverse(s.begin(),s.end());
        return s;
    }

5替换空格

string replaceSpace(string s){
    //统计空格个数
    int count = 0;
    int sOldSize = s.size();
    for(int i = 0; i < sOldSize;i++){
        if(s[i] == ' ')
            count++;
    }
    //扩充字符串s的大小
    s.resize(sOldSize + count * 2);
    int sNewSize = s.size();
    //从后向前替换空格
    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 反转字符串中的单词

原来: abc_def   反转后：  def_abc

先反转每个单词 cba_fed ;在反转整个字符串 def_abc   

28 实现strStr

kmp算法

void getNext(int* next,string& s){
        int j = 0;//j 是前缀末尾
        next[0] = 0;
        for(int i = 1; i < s.size(); i++){ //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) {
        if(needle.size() == 0) return 0;
        int next[needle.size()];
        getNext(next,needle); //next数组中的值表示最长相等前后缀
        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 重复的子字符串

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;
    }