大师兄的数据结构学习笔记(十四）: 词典
大师兄的数据结构学习笔记(十六）: 排序

一、关于串

1. 什么是串

• 串即字符串(String)，是由个字符组成集合, 记作：,其中。
• 字符可以由字母、数字或者其他字符组成。
• 为字符表(Alphabet)，是所有可用字符的集合。
• 为字符串所含字符串的总数，成为的长度，记作。
  

2.特殊串

2.1 空串

• 长度为0的串称为空串(null string)，通常用Ø 表示。

2.2 子串

• 字符串中任一连续的片段，称为子串(substring),记作。
• 起始位置为0，长度为k的子串称为前缀(prefix),记作
• 终止与位置n-1,长度为k的子串称为后缀(suffix),记作

2.3 更多定义

• 空串是任何字符串的子串，也是任何字符串的前缀和后缀。
• 任何字符串都是自己的子串，也是自己的前缀和后缀，称为平凡子串(trivial substring)、平凡前缀(trivial prefix)和平凡后缀(trivial suffix)。
• 字符串本身之外的所有非空字符串、前缀和后缀，称为真子串(proper substring)、真前缀(proper prefix)和真后缀(proper suffix)。

3.串的存储结构

3.1 定长顺序存储

• 即采用静态数组存储串。

char a[5] = "abcde";

• 此方式存储串时，需要预估串的长度提前申请足够的存储空间, 如出申请的长度则串会被截断。

3.2 动态数组存储

• 用堆分配存储。

char* a = new char[5];
delete a[];

3.3 块链存储

• 用链表结构存储。

4. 判等

• 字符串和称作相等，当且仅当二者长度相等,且对应的字符分别相同(对任何都有)。

二、串的匹配算法

• 串匹配(string pattern matching)基于同一字符表的任何文本串(T)和模式串(P)，判定T中是否存在某一字串与P相同。
• 若匹配，则返回该字符串在T中的起始位置。

1. 蛮力算法（Brute Force algorithm）

• 给定一个个字符组成的串（称为文本），一个个字符的串（称为模式）。

• 从文本中寻找匹配模式的子串,蛮力匹配是最直接的方法，将模式串与文本串逐个比对。

  
  

• 如果不匹配，则将模式串后移一位，并将指针回退，重新比较，直至确定可能的匹配位置。

  
  
• 蛮力算法最多迭代轮，且各轮至多进行次比对，故总共需要不超过次比对，时间复杂度为。

int BF_match(char* P, char* T)
{
    size_t i = 0; //模式串字符对齐位置
    size_t j;     //当前接收比对字符的位置
    size_t n = strlen(T); //文本串长度
    size_t m = strlen(P); //模式串长度
    for (i = 0; i < n - m + 1; i++) //从文本串第i个字符开始
    {
        for (j = 0; j < m; j++)  //模式串中的字符逐个比对
        {
            if (T[i + j] != P[j]) break; //若不匹配，则模式串整体右移一个字符继续匹配
        }
        if (j >= m) break; //若匹配则跳出循环
    }
    return i;
}

2. KMP算法

• 由于蛮力算法在每一轮的m次对比中，一旦发现失配，文本串和模式串的字符指针都要回退，并从头开始下一轮尝试，在应对大型数据时效率低。
• 因此，可以通过记录前一轮迭代中已经成功匹配的信息，通过减少重复匹配提高效率,实现仅仅后移模式串，比较指针不回退。

• 如果指针在某个位置发现不匹配。

  
  
• 并且模式串左右两端有两个子串是完全匹配的,这两个子串称为模式串的公共前后缀。
  
• 公共前后缀必须是最长的真前缀和真后缀
  
• 则直接移动模式串的公共前缀到公共后缀所在的位置。
  

• 如果匹配时模式串超出文本串，则匹配失败。

  
  
  
  

2.1 next表

• 实际对于公共前后缀，可以只关注模式串。

  
  

• 假如第一位不匹配，则将模式串向右移动一位，并从指针第一位开始比较。

  
  
  
  
  image.png

• 假如第二位不匹配，由于公共长度小于1，则从指针第一位开始与主串当前位比较。

  
  
  
  

• 假如第四位不匹配，公共模式串后移，从指针第二位开始于珠串当前位比较。

  
  
  
  
  image.png

• 以此类推，获得全部的比较数据。

  
  

• 将第一位标注位0，则可以获得next表。

  
  
• 这样如果任意位置不匹配，即可对照next表快速获得指针位置。

int* buildNext(char* P)
{
    size_t m = strlen(P), j = 0; //主指针
    int* N = new int[m]; //next表
    int t = N[0] = -1; //模式串指针
    while (j < m - 1)
    {
        if (0 > t || P[j] == P[t]) //如果匹配
        {
            j++;
            t++;
            N[j] = (P[j] != P[t]?t:N[t]);
        }
        else //失配
        {
            t = N[t];
        }
    }
    return N;
}

int KMP_match(char* P, char* T)
{
    int* next = buildNext(P);
    int n = (int)strlen(T), i = 0; //文本串指针
    int m = (int)strlen(P), j = 0;//模式串指针
    while (j < m && i < n)
    {
        if (0 > j || T[i] == P[j]) //若匹配
        {
            i++;
            j++;
        }
        else
        {
            j = next[j]; //右移
        }
    }
    delete[] next; //释放next表
    return i - j;
}

3. BM算法

• 与KMP算法类似，BM算法也需要充分利用以往的比对信息，使P向右移动尽可能远的距离。

  
  
• BM算法的模式串P与文本串T的对准位置依旧自左向右推移，而在每一个对准位置却是自右向左地逐一比对个字符。
• 在比对过程中一旦失配，则将P右移一段距离并再次与T对准，然后重新一轮自右向左的扫描比对。

int BM_match(char* P, char* T)
{
    int* bc = buildBC(P); //bc表
    int* gs = buildGS(P); //gs表
    size_t i = 0; //模式串相对于文本串的起始位置
    while (strlen(T) >= i + strlen(P)) 
    {
        int j = strlen(P) - 1; // 模式串最后一个字符
        while (P[j] == T[i + j]) //从右向左比对
        {
            if (0 > --j)break;
        }
        if (0 > j) {
            break;
        }
        else {
            i += __max(gs[j], j - bc[T[i + j]]); //位移量根据BC表和GS表选择最大者
        }
    }
    delete[] gs;
    delete[] bc;
    return i;
}

3.1 坏字符策略

• 在a和b中，若P当前在文本串T中的对齐位置位i,且在这一轮自右向左将P与substr(T,i,m)的比对过程中，在P[j]处首次发现失配，则X称为坏字符(bad character)。
• 此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。
• 此外，如果"坏字符"不包含在模式串之中，则最右出现位置为 -1，坏字符针对的是文本串。
• 若P与T的某哥字符串匹配，则必然在处匹配。
• 反之，若对准的字符不是X，则必然失配。
• 所以如c中，只需要找出P中的每一个字符X，分别与对准，并执行一轮自右向左的扫描比对。
  

• 如果没有坏字符，则整体移到坏字符后方

  
  

• 如果包含坏字符，则将bc表中的最后一个坏字符对齐。

  
  

1) bc表

• 若P中包含多个X，则仅尝试P中最靠右的字符X。
• 若P中最靠右的字符X为，则P的右移量为j-k。
• 任一给定模式串P, k值取决于字符串，可将其看作字符表到整数的一个函数:
• 故如当前对其位置为i, 一旦出现坏字符Y,则重新对齐与。
• 预先将函数bc()整理为一份查询表，称为BC表。

int* buildBC(char* P)
{
    int* bc = new int[256]; //BC表
    for (size_t j = 0; j < 256; j++)
    {
        bc[j] = -1; //初始化
    }
    for (size_t m = strlen(P), j = 0; j < m; j++)
    {
        bc[P[j]] = j; //将字符P[j]的BC项更新为j
    }
    return bc;
}

3.2 好后缀策略

• 将每轮比对中的连续的若干次成功匹配，对应于模式串P的一个后缀，称为好后缀(good suffix)。
• 当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为 -1，好后缀针对的是模式串。
  
• 如(a)(b),设自右向左的扫描适配位置为:
• T中匹配的子串为:
• 好后缀为:
• 好后缀长度为,故当时，必非空且
• 设某整数k，是P右移j-k单元，并使P[k]与T[i+j]对其之后，P能与T的某一子串匹配，即
• 若记：则.
  

• 如果发现好后缀，则将目标串与好后缀对齐。

  
  
  
  

• 如果无法找到匹配好的后缀，则找一个匹配的最长的前缀与目标串对齐。

  
  

3.2.1 gs表

• 与bs表类似，gs表通过预处理将模式串P事先转换为一张表记录对应的位移量。
• 其中

1) 蛮力算法

• 对于每个好后缀,按照自后向前的次序()与P的每个字符串逐一对其，如果匹配，对应的位移量即为gs[j]的取值。
• 此方法可能需要的时间，效率很低。

2) ss表

• 表示在P[0,j]的所有后缀中，与P的某一后缀匹配的最长者。
• 是表示在P[0, i]的所有后缀中，与P的某一后缀匹配的最长长度(也就是)，即最长匹配后缀(maximum matched suffix)的长度。

情形一：如果对应的最长匹配后缀延伸到了P的最左侧，则有。

• 此时，模式串中所有的秩为i的字符，如果有，则MS[j]都是在该处匹配失败的一个候选对齐位置，对应了上面好后缀的第二种情形，此时它们的移动距离距离都是m - j - 1，即m - j -1必然是gs[i]的一个候选。(不适用于的情形，因为首位两个子串完全匹配，在该位置对齐后的下一次匹配必然会失败。)

情形二: 是的真后缀，此时有。

• 此时只能作为在位置处比对失败的候选对齐位置。

int* buildSS(char* P)
{
   int m = strlen(P); //P的长度
   int* ss = new int[m]; //ss表
   for (int lo = m - 1, hi = m - 1, j = lo - 1; j >= 0; j--)
   {
       if ((lo > j) && (ss[m - hi + j - 1 <= j - lo])) //情形一
       {
           ss[j] = ss[m - hi + j - 1]; 
       }
       else
       {
           hi = j;
           lo = __min(lo, hi);
           while ((0 <= lo) && (P[lo] == P[m - hi + lo - 1]))
           {
               lo--;
           }
           ss[j] = hi - lo;
       }
   }
   return ss;
}

int* buildGS(char* P)
{
    int* ss = buildSS(P); //ss表
    size_t m = strlen(P);
    int* gs = new int[m]; //gs表
    for (size_t j = 0; j < m; j++)
    {
        gs[j] = m; //初始化
    }

    for (size_t i = 0,j = m - 1; j < UINT_MAX; j--) //逆向逐一扫描字符串P[j]
    {
        if (j + 1 == s[j])
        {
            while (i < m - j - 1)
            {
                gs[i++] = m - j - 1;
            }
        }
    }

    for (size_t j = 0; j < m - 1; j++)
    {
        gs[m - ss[j] - 1] = m - j - 1;
    }
    delete[] ss;
    return gs;
}

4. Karp-Rabin算法

• Karp-Rabin算法对模式串进行哈希运算，并将哈希值与文本中子串的哈希值进行比对。
• 如果哈希值比对匹配，再将哈希匹配的部分逐位比对（因为要考虑哈希碰撞）。
• 为此，需要找到一个哈希函数 ，将字符串转换为数字。

• 复杂度为，但在实际使用过程中的复杂度通常被认为是。

const size_t d = 256;

void KR_match(char* P,char* T,int q)
{
    size_t m = strlen(P);
    size_t n = strlen(T);
    size_t j;
    
    int p = 0; //P的哈希值
    int t = 0; //T的哈希值
    int h = 1;

    for (size_t i = 0; i < m - 1; i++)
    {
        h = (h * d) % q;
    }

    for (size_t i = 0; i <m; i++) //计算哈希值
    {
        p = (d * p + P[i]) % q;
        t = (d * t + T[i]) % q;
    }

    for (size_t i = 0; i <= n - m; i++) //逐一比对哈希值
    {
        if (p == t) //如果哈希值相等
        {
            for (j = 0; j < m; j++)
            {
                if (T[i + j] != P[j])break;
            }

            if (j == m)
            {
                cout << i << endl;
            }
        }

        if (i < n - m)
        {
            t = (d * (t - T[i] * h) + T[i + m]) % q;
            if (t < 0)
            {
                t = t + q;
            }
        }
    }
}