算法训练营 字符串总结

20200409 字符串总结

• 基本概念：(真)子串、(真)前缀、(真)后缀
  空串(null string) 与 由空格字符' '组成的串完全不同
  空串是任何字符串的子串

• 常用串模式匹配(string pattern matching)算法:Brute-Force 、KMP、BM(BC策略/GS策略)

• 如何评价一个模式匹配算法的性能
  书本P308 如果简单的随机生成text和pattern，那么这一匹配成功的概率非常非常小，该策略不足以有效覆盖成功匹配情况，故无法反应其总体性能。

• Brute-Force
  注意两个版本相比于自己所写，其对于处理空串的优势，不用单独判断，结果位置处与平凡情况一起判断

  • 版本一

    //text ：  ----i-j----------i---
    //pattern：-----0-----------j---
    int match(string text,string pattern){//对于text或者patter为空 均能正确处理
    int n = text.size();
    int m = pattern.size();
    int i = 0,j = 0;
    while(i<n && j<m){
        if(text[i]==pattern[j]) {++i;++j;}
        else {i = i-j+1; j = 0;}
    }
    //return i-j;//原书写法：返回结果，由调用者判断
    if(i-j<=n-m) return i-j;//修改结果：成功返回匹配首字符位置，失败返回-1
    else return -1;
    //如果成功匹配，说明j = m,i<=n;i-j<=n-m;
    //如果匹配失败，说明j<m,i=n;i-j>n-m
    }

  • 版本二

    //------i------i+j----
    //------0-------j-----
    int match(string text,string pattern){//同样的对于text或者pattern为空都能正确处理
    int n = text.size();
    int m = pattern.size();
    int i=0,j=0;
    for(;i<n-m+1;++i){
        for(j=0;j<m;++j){
            if(text[i+j]!=pattern[j]) break;
        }
        if(j==m) break;
    }
    //return i;//原书写法，由调用者判断
    if(i<n-m+1) return i;
    else return -1;
    //如果匹配成功，说明i<n-m+1;
    //如果匹配失败，说明i=n-m+1;
    }

• KMP算法（经验+教训）
  构造next表，将经验(已经成功匹配部分)转换成记忆，从而能够在失配位置快速移动，避免文本串指针回溯
  由版本一演变而来

  //-----i-j-------i-----
  //------0--------j-----
  int match(string text,string pattern){
    vector<int> next = buildNext(pattern);
    int n = text.size();
    int m = pattern.size();
    int i = 0 , j = 0 ;
    while(i < n && j < m){
        if(j < 0 || text[i] == pattern[j]) {++i; ++j;}//注意j<0
        else {j = next[j];}//区别仅在于此
    }
    if(i - j < n - m) return i - j;
    else return -1;
  }

  //构造next表（只考虑到经验）
  vector<int> buildNext(string pattern){//pattern 非空
    int m = pattern.size();
    vector<int> next(m);
    int t = next[0] = -1;//t最终记录当前元素j的next[j]
    int j = 0;
    while(j<m-1){//注意这里j<m-1
        if(t<0 || pattern[j] == pattern[t]){
            ++j;++t;
            next[j] = t;//此处可改进
        }
        else t = next[t];//t = next[t]
    }
    return next;
  }

  //改进的next表（经验+教训）
  //假设在位置j失配，那么将会用next[j]替代j，但是因为p[j]与原来不匹配，那么p[next[j]]就不能再等于p[j]（这就是教训）
  vector<int> buildNext(string p){//p非空
    int m = p.size();
    vector<int> next(m);
    int t = next[0] = -1;
    int j = 0;
    while(j<m-1){
        if(t<0 || p[j]==p[t]){
            ++j;++t;
            next[j] = (p[j]!=p[t]?t:next[t]);//改进在此
        }
        else t = next[t];
    }
    return next;
  }

• BM(Boyer-Morre)

  • BC策略（Bad Character）

  • GS策略（Good Suffix）