字符串的存储和常见操作实现

// 求字符串的长度
int strlen(char d []){
    int i = 0; 
    while(d[i] != '\0'){
        i++;
    }
    return i;
}

// 字符串的拷贝操作
char *strcpy(char *d, char *s){
    int i = 0;
    while(s[i] != '\0'){
        i++;
        d[i] = s[i];
    }
    d[i] = '\0';
    return d;
}

// 字符串的比较
int strcmp(const char *s1, const char *s2){
    int i = 0;
    for(i = 0; s1[i] == s2[i]; i++){
        if(s1[i] == s2[i] && s1[i] == '\0')
            return 0;
    }
    return (s1[i] - s2[i]) / abs(s1[i] - s2[i]);
}


class String{
private:
    char* str;
    int size;
public:
    String(char *str){
        size = strlen(str);
        str = new char[size + 1];
        assert(str != NULL);
        strcpy(this->str, str);
    }
    ~String(){
        delete [] str;
        str = NULL;
    }
    int size(){
        return size;
    }
    char* c_str(){
        return str;
    }
    String operator=(String &s){
        if(str != s.size()){
            delete []str;
            str = new char[s.size() + 1];
            assert(str != NULL);
            size = s.size();
        }
        strcpy(str, s.c_str());\
        return *this;
    }
    String substring(int start, int num){
        assert(start >= 0 && start + num - 1< size);
        char * newstr = new char[num + 1];
        int i = 0;
        while(i != num){
           newstr[i] = str[start + i];
           i++;
        }
        newstr[i] = '\0';
        return String(newstr);
    }
    void reverse(){
        int start = 0;
        int end = size - 1;
        while(start != end){
            int tmp = str[start] - str[end];
            if(tmp > 0){
                str[start] = str[start] - tmp;
                str[end] = str[end] + tmp;
            }
            else if(tmp < 0){
                str[end] = str[end] - tmp;
                str[start] = str[start] + tmp;
            }
            end--;
            start++;
        }
    }
}

字符串的模式匹配

朴素模式匹配法（穷举法）

字符串匹配就是给定一个字符串，想要判断一下在该字符串中是否存在有一个子串，有则返回第一个匹配字符的下标，否则返回-1

int fidPat_3(string T, string P, int startIndex){
    for(int g = startIndex; g <= T.length() - P.length(); g++){
        for(int j = 0; (j < P.length() && P[j] == T[g + j]); j++){
            if(j == P.length()-1){
                return g;
            }
        }
    }
    return -1;
}

该算法最坏情况下的复杂度是 O(m × n), m 为长串的长度，n为短串的长度。

快速模式KMP算法

KMP算法就是在朴素匹配算法的基础之上，对每次滑动的位数 n 进行了提前的计算，减少了不要的冗余计算。

而这个滑动的位数计算的思想就是先建立一个关于模式串P中每一个字符的特征向量表。

其中next数组就是所谓的特征向量表。当 j ！= 0 时，向量元素值的含义就是在模式串本身的从0到 j - 1的子串中，首尾的的连续等长子串相等时的最大长度值k。

这样当模式串的第 j + 1个元素匹配错误的时候，我们就可以直接确定下一步滑动的位数为 j - k 位。

理由是模式串首部的前k个字符和模式串的【j - k ： j 】的子串相匹配，下一次匹配时，可以用首部的串代替尾部的子串，然后减少比较次数。

int KMPMatching(string T, string P, int *N, int start){ // N 为特征向量
    int j = 0;  // 模式串P的比较位置
    int i = start; // 目标串的比较位置
    int plen = P.length();
    int tlen = T.length();
    if(tlen - start < plen)
        return -1;
    while(j < plen && i < tlen){
        if(j == -1 || T[i] == P[j]){
            i++;  // 如果两个比较位置相同，那么位置都递增
            j++;
        }
        else{  // 模式串在位置 j 发生了不匹配
            j = N[j];  // 模式串的比较位置需要更新为特征向量的值
        }
    }
    if(j >= plen){  //匹配成功，返回匹配子串的起始位置
        return (i - plen);
    }
    return -1;
}

int* fineNext(string P){
    int j, k;
    int m = P.length();
	assert(m > 0);
    int *next = new int[n];
    assert(next != NULL);
    next[0] = -1;
    j = 0; k = -1;
    while(j < m - 1){
        while(k > 0 && P[k] != P[j]){
            k = next[k];
        }
        j++; k++; next[j] = k;
        // 进行优化
        if (P[k] == P[j]){
            next[j] = next[k];
        }
        else next[j] = k;
    }
    return next;
}

数据结构 | 字符串string 学习

2019-03-26

数据结构 | 字符串string 学习

字符串的存储和常见操作实现

字符串的模式匹配

朴素模式匹配法（穷举法）

快速模式KMP算法