第十一章：串

第十一章：串

ADT

长度小于字符串长度的前缀和后缀分别叫做真前缀和真后缀。

串匹配

文本串T：长度为n；模式串P：长度为m。

一般情况下n远大于m，判断T中是否存在某一子串与P相同，如果存在则返回该子串在T中的起始位置，这一过程叫做串匹配。

为了评估串匹配算法的性能，如果随机生成T和P，P有2^m种不同的情况，而T中长度为m的子串只有n – m + 1种情况，匹配成功的概率极低。

不妨从随机的T中随机取出长度为m的子串作为P来分析匹配成功的复杂度。

蛮力匹配

蛮力匹配的思想是首先考察T中以第一个字符开始长度为m的子串与P是否匹配，不匹配再考虑以第二个字符开始长度为m的子串是否匹配，直到匹配成功或者遍历到T的最后一个长度为m的子串依旧不匹配，匹配失败。

版本一：

这个版本的蛮力算法i指向当前T中正在匹配字符在T中的位置，j指向P中正在匹配的字符在P中的位置。算法过程：T[i] == P[j]时当前字符匹配，i和j均移到下一位置；否则说明不匹配，j应该从0开始匹配，i则应该回到之前匹配起始位置的后一位置继续匹配。上一次匹配失配于T的第i个字符与P的第j个字符不等，此时i与j对齐，T中i – j的字符与P中下标为0的字符对齐，所以下一轮匹配T必开始于i-j的后一个位置即i = i – j + 1.

观察循环的退出条件，如果是j达到m导致退出说明匹配成功，如果是j未到m而i达到n导致循环结束说明匹配失败。也可以通过返回值来判断匹配的结果，匹配失败时，i的下标必然是n – 1，j的下标是0，所以会返回n – 1表示匹配失败，如果成功了i – j返回的是匹配成功与T的i – j的位置，此时i – j必然不超过n – m。

版本二：

这个版本的i表示每轮匹配时模式串中长度为m的子串首字符的位置，也就是说T[i]始终与P[0]对齐，j同样表示匹配到P中第j个字符。所以对i的枚举起始于0，终止于n – m。每轮匹配中，如果由于T[i]和P[0]始终对齐，所以匹配时只需j++去比较T[i+j]和P[j]是否匹配就可

以了。失配时内存循环退出，i继续考察下一个位置，j继续从0开始循环，如果最后匹配成功，返回的i必然不超过n – m，反之则匹配失败。

蛮力算法在最坏情况下一轮匹配即成功，复杂度为O（m）；在最坏情况下每轮匹配前m-1个字符均匹配，最后一个字符一直失配，导致每轮需要比较m次，重复n – m + 1轮，时间复杂度为O（nm）。

这种最坏情况在字符表规模不大时出现概率越高，比如二进制串，模式串越长，最坏情况的后果也就越严重。当字符表规模较大时，蛮力算法的时间复杂度接近于线性的O（n）。

KMP算法：从记忆力到预知力

蛮力算法低效的根源在于T中已经比对过的字符在下一次匹配中将再次参与比对。

不变性：尽管在某轮匹配中，字符串匹配失配于T[j]和P[j]，但是在此之前的子串必然都是相等的，也就是T[i-j,i) = P[0,j]。

记忆力：某轮失败的匹配中，我们已成功获知T[i-j,j)的字符，所以下次匹配过程无需再重新比对它们。

知道了文本串T[i-j,j)的字符是什么，便不必将i完全回退到起点，只需将j回退到某个位置t，使得P[0,t)与T对齐的部分是匹配的。

KMP算法：查询表

根据前面的分析，在匹配失败时，i不变，j移动到模式串前面的某位置t上使得模式串中以t-1为末尾的真前缀与文本串中以i-1为末尾的真后缀完全相等，而T中i的前缀与P中j的前缀完全相同，故可以理解为P中以t-1为末尾的真前缀与P中以j – 1为末尾的真后缀相同，故t的位置与文本串T无关，仅与P有关。

为此，我们只需要实现构建查询表，确定下在某个位置失配时将跳转到哪个位置即可。

KMP匹配的主算法较为简单，首先构建next表，然后自左向右比对字符，失配时j转到next[j]，匹配时i，j携手共进。这里的另一种情况i，j在j小于0时也携手共进的情况后面再分析，因为此时j = -1.

KMP算法：理解next表

根据之前的分析，模式匹配失配于T[i]与P[j]，此时需要将j移动到t的位置，而之所以不用比对t之前的字符，是因为模式串中t之前长度为t的前缀与j之前长度为t的后缀完全相等。即P[0,j)中，所有匹配的真前缀和真后缀长度皆可作为t。

既然t并不唯一，为了安全，不妨选取最小位移量的t，P从j移到t，（t < j）,位移量是j – t，即选取t最大的一个位移最小，t代表的不仅是j马上要转向的位置，还是P[0,j)中真前缀和真后缀相等的长度，故t是与真后缀相同最长真前缀的长度。

失配时j > 0的情况，即不是在首字符失配的，此时由于空串是任何非空串的真子串，所以即使找不到长度大于0的相等的真前缀和真后缀，也可以令t = 0，即模式串中首字符与T[i]继续比对，此时t = 0也就是真前缀长度为0.

如果j = 0，P[0,j)本身就是空串，自然找不到真子串了，意味着上一轮匹配失配于第一个字符的比对，此时文本串中i应该加一，j应该等于0来进行下一轮匹配。回顾KMP算法，字符在失配时j = t，i不变，为了下一轮匹配开始，j能够变成0，i能够加一，只需要在字符串最左侧-1的位置设置个假想的哨兵，该哨兵与所有其他字符都匹配，匹配时j++需要等于0，i也需要++，所以在上一轮的失配中，j应该等于t等于-1，从而得出j = 0，即第一个字符即失配情况的t值就是-1.这也是之前KMP算法中匹配时i，j携手共进的条件除了T[i] = P[j]还有个j < 0的缘故。

KMP算法：构造next[]表

在之前的分析中，我们知道了next[0] = -1,这意味着只要我们能够根据next[j]求出next[j + 1],便可成功的构造出next表了。

比如

 

    0 1 2 3 4 5 6 7

T: a b c d a b c e

P: a b c d a b c d

某次匹配在j = 7处失配，next[7] = 3,于是快速将j移动到下标为3的位置继续匹配.

T: a b c d a b c e

P:            a b c d a b c d

这是因为abcdabc的真前缀abc与真后缀abc相等.

回想某次在j = 6处失配的过程。

    0 1 2 3 4 5 6 7

T: a b c d a b d e

P: a b c d a b c d

某次匹配在j = 6处失配，next[6] = 2,于是快速将j移动到下标为2的位置继续匹配.

T: a b c d a b d e

P:            a b c d a b c d

这时我们已经知道了P的真前缀ab与真后缀ab相等了，即P[0,2) = P[4,6),于是在j移动到7时，P[0,3) = P[4,7)只需要满足P[2] = P[6]的条件即可，也就是说，在求next[j+1]的最大的真前缀=真后缀的长度时，只需要先考察P[j]和P[t]是否相等，（P[j]是求next[j]时真后缀的后一个字符，P[t]是真前缀的后一个字符），只要它俩相等，则在求next[j+1]时，最大的真前缀=真后缀的长度便可增加一个单位，即next[j + 1] = next[j] + 1当且仅当P[j] = P[t] =P[ next[j]]。

更大的问题在于P[j] != P[next[j]]时。

比如：

:   0 1 2 3 4 5 6 7 8

T: a b a c a b a c e

P: a b a c a b a b d

我们知道next[7] = 3

T: a b a c a b a c e

P:            a b a c a b a b d

但是在求next[8]时，发现P[7] = b != c=P[3]，此时next[8]的最长的真前缀=真后缀的长度不能超过next[7]了我们需要继续将P右移，直至下一次对齐：

T: a b a c a b a b e

P:                  a b a c a b a b d

当t = 1时，P[0,8)的真后缀ab恰好与真前缀ab相等，可以发现，这一过程等同于P[j]与P[next[j]]在匹配过程中失配了，需要将j移动到新的t来重新匹配，我们需要在P[0,next[j])中找到新的t来使得P[0,next[j])中长度为t的真前缀和真后缀相等，不难发现，这里的t就等于next[next[j]].

所以当P[j] != P[next[j]]时，我们需要继续比对P[j]与P[next[next[j]]],直到相等为止。

构建KMP表的算法需要一开始给N[0]赋初值-1，然后实现递推式，每次比对P[j]和P[next[j]]，相等则令t = next[j] = next[j – 1] + 1,t始终等于上一次匹配成功时的next值，所以匹配成功时将t + 1赋给N[j]即可。

KMP算法：分摊分析

令k = 2*i – j，i，j的初值都是0，所以k的初值也是0.当匹配时i和j都++，此时k也恰好加1，不匹配时i不变，j必然减少，所以k也至少增加1，所以总的比对此时不会超过k，而i最终指向的值必然小于n，j指向的值也是常数级别的，所以k最终的值是O（n）级别的，构建next数组的函数与KMP匹配过程一致，比对次数是O（m）的，所以总的时间复杂度是O（n + m）。

对于k = 2*i – j的含义，观察可知，每次成功的比对，i都会+1，所以i始终记录着成功比对的次数；而在成功比对时，i和j均自增，i – j保持不变，失败的比对时，i不变，j减小，i-j会增加，所以i – j可以作为失败比较次数的上界，这也是k = 2*i – j的原因。

KMP算法：再改进

在上图的例子中，KMP算法尽管避免了重复的比对，但是P的右移依旧十分缓慢，这是因为，尽管KMP算法吸取了前面字符成功比对的经验，却没有吸取T[i]与P[j]失配的教训，这导致后面明明知道在P[t] = P[j]的情况下还要将j移动到t的位置。

改进后的next表的构建，只是把N[j] = t的语句修改为了N[j] = ( P[j] != P[t] ? t : N[t]);

如果叉开来看N[j+1]和N[j]的关系，可以得到P[j] != P[N[j]]时，继续考察N[N[j]]，即t = N[t];

若P[j] == P[N[j]]（或者t<0），当P[j+1] != P[N[j] + 1]时，N[j + 1] = t + 1;当P[j+1] == P[N[j] + 1]时，N[j + 1] = N[N[j] + 1],注意不是转向N[N[j]] + 1而是转向N[N[j] + 1]。也就是当P[j] == P[N[j]]并且j + 1要转向的位置的元素与P[j+1]不等时，就转向它，否则再对该位置取个Next。这是因为如果P[j] != P[N[j]]，我们继续考察N[N[j]]是因为真前缀长度无法延长，而P[j+1] == P[N[j] + 1]时真前缀长度可以延长，只是马上要转向的字符和原先的字符相等，我们放弃了这次比对，转而找到以待转向字符为末尾的字符串的最大相等的真前缀和真后缀。

例：

秩	0	1	2	3	4	5	6	7	8
P	a	b	a	c	a	b	a	b	d
Next	-1	0	0	1	0	1	2	3	2
改进后的Next	-1	0	-1	1	-1	0	-1	3	2

 

求next表，判断当前字符上一个字符与上一个字符的next是否相等，相等则等位上一个字符的next+1.

改进后的next设为N1，判断当前字符j与next[j]是否相等，相等则等于N1[j],不等则等于next[j]。也就是说，N1的值可能等于next的值也可能转向之前N1的值。

KMP算法在字符表规模不大的情况，比如二进制串优势明显，但是一旦字符集规模大，蛮力算法的效率也是接近线性的了。

BM_BC算法：以终为始

KMP算法更多的是吸取成功匹配的经验，来加速右移，不过，当字符集规模较大时，成功的比对是远小于失败的比对的，与其吸取成功经验，不如善待失败的教训。

对于模式串而言，越靠后的字符可以吸取的教训就越多，观察上图左边的箭头，表示在模式串第一个位置失配，这样的失败可能毫无价值，因为我们会立刻越过这个位置，模式串中不会再有任何字符去与已经越过的文本串中那个字符去比对了；但是如果如果是模式串最后的字符失配了，我们就知道，在右边的箭头上，模式串中只有和刚才比对过的那个字符相等的字符才可能匹配，如果模式串中没有这个字符，就可以一举跳过很多次比对。

在上图的比对中，我们从末字符开始比对，发现名不等于道，而且模式串中也没有道，于是快速越过，重复该比较过程，最后发现所需的比较次数还不到文本串的长度。

BM_BC算法：坏字符

按照之前的设想，在某位置模式串中Y与文本串中X不匹配，于是将模式串右移一定位移，

使得模式串中的X与文本串中的X对齐。

为此，我们需要制作一个bc表来映射出所有字符的秩，以使得在需要某字符来比对时，能够快速右移。

如果P中包含多个X，则为了安全应该使位移尽可能的小，所有应该取最右边的X，如果P中不包含X，则P应该整体越过刚才的比对位置。

还有种情况是找到了最右边的X，但是X在P却在之前失配位置的右边，为了不往左倒退，我们只能将P右移一个字符；当然，可能选在P[j]左侧与之最近的X来与失配的位置对齐更好，但是之前bc表中只有最右边X的位置，我们如果想要找到其他X的位置，需要重新搜索模式串。

BM_BC算法：构造bc[]

构造bc表可以使用画家算法，即一遍初始化，将所以字符的初值都设置为-1（找不到该字符整体越过的哨兵位置），然后遍历一遍模式串，便遍历边给字符出现的位置赋值，后面重复的字符的位置会覆盖掉前面出现过字符的位置，因此，扫描到最后，bc表中每个字符的位置都会是它最后出现的位置。

BM_BC算法的总代码如下：

int* buildBC ( char* P ) { //构造Bad Charactor Shift表：O(m + 256)
   int* bc = new int[256]; //BC表，与字符表等长
   for ( size_t j = 0; j < 256; j ++ ) bc[j] = -1; //初始化：首先假设所有字符均未在P中出现
   for ( size_t m = strlen ( P ), j = 0; j < m; j ++ ) //自左向右扫描模式串P
      bc[ P[j] ] = j; //将字符P[j]的BC项更新为j（单调递增）——画家算法
   return bc;
}

int match ( char* P, char* T ) { //Boyer-Morre算法(简化版，只考虑Bad Character Shift)
   int* bc = buildBC ( P ); //预处理
   size_t n = strlen ( T ), i = 0; //文本串长度、与模式串首字符的对齐位置
   size_t m = strlen ( P ); //模式串长度
   while ( n >= i + m ) { //在到达最右端前，不断右移模式串（可能不止一个字符）
      int j = m - 1; //从模式串最末尾的字符开始
      while ( P[j] == T[i+j] ) //自右向左比对
         if ( 0 > --j ) break; /*DSA*/showProgress ( T, P, i, j ); getchar();
      if ( j < 0 ) //若极大匹配后缀 == 整个模式串，则说明已经完全匹配，故
         break; //返回匹配位置
      else //否则，根据BC表
         i += __max ( 1, j - bc[T[i+j]] ); //相应地移动模式串，使得T[i+j]与P[bc[T[i+j]]]对齐
   }
   delete [] bc; //销毁BC表
   return i;
}

注意这里每次失配后重新比对，j始终从最右边字符开始自右向左比对，而不是从之前失配的位置开始比对，这是为了保证算法的正确性。

比如：

11265356

12645

第一次失配 与4！=6，然后模式串右移使得6对齐。

11265356

  12645

此时新一轮的比对依旧是从字符串末尾开始，而不是从失配的6开始。

BM_BC策略：性能分析

BM_BC算法的最坏情况是每次匹配的最后一个字符模式串中都没有，因此每轮匹配比对一次就会右移m位，一共需要O（n / m）的时间。单次匹配概率越小，P越长，BC算法优势越明显，虽然是以二进制作为例子，但是BM_BC算法适用于字符集规模大的情况。

最坏情况则是每轮自后向前比对前m – 1次都是成功的，只有首位置失配，以至于模式串缓慢的右移，与蛮力算法类似，退化为了O（n*m），在字符集规模小，比如二进制串中，这种情况越容易出现，这是因为BM_BC算法善于吸取教训，却不善于利用经验。

BM_GS算法：好后缀

在BM_BC策略中，bc表中存储的是字符最后出现的位置，因此，在上面的匹配中，第一轮失配于C与H的比对，在bc表中寻找C发现最后一个C在失配位置的后面，不能移动，遂将模式串右移一个单位；第二轮匹配失配于H与C的比对，同样bc表中H的位置依旧在C的后面，模式串继续右移一个单位，失配于A与H，此时bc表中A的位置在H前面，右移模式串使模式串中最后一个A与文本串的A对齐，此时，匹配成功。

可以发现，BM_BC策略的瑕疵所在就是只能存储字符出现的最后的位置，而正如同KMP算法，这里第一轮匹配时，对ATCH的比对都是成功的，我们可以借鉴这次成功的比对。

在自后向前的比对中，模式串失配于Y的位置，而且Y后面的位置都是匹配的，现在只需要将模式串右移一定距离使得X后面的位置依旧匹配，并且新来的与X对齐的位置不能再是Y了。这里gs表存储的是在某位置失配时模式串需要右移的位移量。

如果存在多个这样匹配的子串，则应该选择位移量尽可能小的。

如果模式串中不存在这样匹配的子串，则应该尽可能的与之前匹配子串的后缀匹配上尽可能多的字符。

BM_GS算法：构造gs表

为了构造gs表，首先引入MS[j]的概念，MS[j]即P[0.j]的所有后缀中，与P的某一后缀匹配的最长者，比如MS[8]等于RICE，MS[2]等于ICE，而ss[j]则表示MS[j]字符串的长度。

上图是理解ss表到gs表的关键，不妨还以刚才的例子来分析：

第一种情况，ss[j] = j + 1，也就是说P中以秩为j的字符结尾的前缀都可以与P的某一后缀匹配，比如j = 2时，ss[j] = j + 1 = 3，ICE这个前缀可以与ICE这个后缀完全匹配，这意味着，失配于位于11的R时，将模式串右移12个单位会是一个方案，即12是gs[11]的一个候选者，为什么是候选者而不是确定的值，因为这时可能会考虑其他的位移，比如6.在位于3的D处失配时，同样可以将模式串右移12个单位来进行新一轮匹配，这时模式串已经越过了之前失配的位置了，只需要保证P的前缀与失配时P的后缀相等即可，无须再考虑之前失配的位置，有多少位置是这种情况呢？i < m – j – 1，也就是上图一旦秩小于12的的字符失配都可以移动m – j – 1=12位。

第二种情况：ss[j] <= j，说明以秩为j字符为末尾的子串虽然可以与P的某后缀匹配，但是这个子串不是P的前缀了。比如j = 8时，ss[j] = 4,可以通过右移6个位置使得RICE与末尾的RICE匹配，但是此时以E为结尾的子串不是P的前缀了，这时，只有位于P的后缀RICE前的字符P失配时才会考虑将P右移6个位置，由于此时ms[8]不是P的前缀，右移后尽管与后缀匹配，但是此时秩为4的字符被移动到了失配的位置依旧要与文本串中字符重新比对，此时秩为4的字符不一定等于文本串中对齐的字符，但是一定不会等于之前与之对齐的字符P，否则ss会进一步延长。为什么这种情况只有与之匹配后缀的前一个字符失配时才能考虑这样的位移呢？因为比如秩为9的字符失配了，我们依旧右移6个位置，会发现尽管末尾的RICE是匹配的，但是前面的P字符却与空格字符不等，无法匹配。

第一种情况：

ICED RICE PRICE

                        ICED RICE PRICE

第二种情况：

ICED RICE PRICE

            ICED RICE PRICE

下面的问题在于构造ss表，找到每个字符为末尾的后缀子串与P的后缀匹配的最大长度，显然二重循环需要平方级别的时间，下面是线性时间内构造ss表的算法。

int* buildSS ( char* P ) { //构造最大匹配后缀长度表：O(m)
   int m = strlen ( P ); int* ss = new int[m]; //Suffix Size表
   ss[m - 1]  =  m; //对最后一个字符而言，与之匹配的最长后缀就是整个P串
// 以下，从倒数第二个字符起自右向左扫描P，依次计算出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 ) ) //情况一（教材代码）
      if ( ( lo < j ) && ( ss[m - hi + j - 1] != j - lo ) )//自己修改的代码
         ss[j] =  ss[m - hi + j - 1]; //直接利用此前已计算出的ss[]
      else { //情况二
         hi = j; lo = __min ( lo, hi );
         while ( ( 0 <= lo ) && ( P[lo] == P[m - hi + lo - 1] ) ) //二重循环？
            lo--; //逐个对比处于(lo, hi]前端的字符
         ss[j] = hi - lo;
      }
   return ss;
}

PS:如果只看教材的分析我觉得没几个能看得懂那么抽象的说明，虽然算法本身不难，但是在没有具体的说明前，恐怕只有手动走一遍算法的流程才能够理解该算法了。

还是以这幅图为例，自右向左构造ss表，像找到ss[13] = 0后，我们可以确定字符C是不等于末尾的E的，对前一个字符I的ss值的求解没有借鉴意义，对于这种没有可以借鉴的经验的比对而言，为了确定ss值，我们都是先将j位置的字符与末字符比较，不等则ss值就是0,；相等的情况比如j = 8，此时E = E，继续考察前面的元素，C = C，I = I，R = R，这时我们可以维护一个区间(lo,hi],表示区间内的子串和末尾的子串是匹配的，当lo = 4时，不再匹配，于是ss[8] = hi – lo = 4,对于j = 8而言，其与末尾子串匹配的最大后缀是(4,8]。

知道j = 8时，(4,8]位置的子串是可以与末尾匹配的，所以在下一步求j = 7的ss值时，我们本来是需要先将C与P的末字符比对，相等则继续比对之前的字符的，但是此时j = 7之前的RIC字符已经确定与11 – 13的RIC字符相等了，我们在计算j = 13时，已经做了这样的比对，所以只要ss[13]的值小于3，说明RIC这个子串不会全部与P的后缀匹配，如此就可以直接令ss[7] = ss[13]了；如果ss[13] = 3,这种情况教材中是归入上一种情况的，貌似这里教材分类错误已记入了勘误，因为我们在j = 8那次匹配中只确定了RICE是与末尾一样的，I前面的字符不一样，所以ss[13] = 3,说明在j = 13时，匹配到10时失配了，但是由于10处的字符与4处的字符不同，所以4处的字符有可能增加j = 7时的ss长度，需要继续比对；如果这时ss[13]>3呢，说明不仅11 – 13的字符可以匹配后缀，前面的字符还可以匹配后缀，而我们在j = 8时那次匹配确定了R之前的字符字符肯定不等，所以这时依旧可以令ss[7] = ss[13].

复杂度分析：内层循环每执行一次lo必减1，而lo减至负数便不再执行内循环，因此内循环累计执行不过O（m）次，总的复杂度也是O（m）。

由ss表生成gs表的算法如下：

int* buildGS ( char* P ) { //构造好后缀位移量表：O(m)
   int* ss = buildSS ( P ); //Suffix Size table
   size_t m = strlen ( P ); int* gs = new int[m]; //Good Suffix shift table
   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 == ss[j] ) //若P[0, j] = P[m - j - 1, m)，则
         while ( i < m - j - 1 ) //对于P[m - j - 1]左侧的每个字符P[i]而言（二重循环？）
            gs[i++] = m - j - 1; //m - j - 1都是gs[i]的一种选择
   for ( size_t j = 0; j < m - 1; j ++ ) //画家算法：正向扫描P[]各字符，gs[j]不断递减，直至最小
      gs[m - ss[j] - 1] = m - j - 1; //m - j - 1必是其gs[m - ss[j] - 1]值的一种选择
   delete [] ss; return gs;
}

 

BM_GS算法：综合性能

采取BC+GS策略来实现BM算法（先构建bc和gs表，每次失配选择两种算法中位移量较大的那个位移）。最好情况下是O（n / m），最坏情况下BC算法有了GS算法的辅助也可以达到O（n + m）的复杂度。

蛮力算法BF在最好情况下匹配失败概率大时复杂度为O（n + m），最好情况下是O（n * m）。

KMP算法稳定在O（n + m），单纯的BM_BC算法最好情况下是O（n / m），最坏情况下是O（n*m），配合GS算法使用最坏情况可优化至O（n + m）。

BF、BM_BC算法在字符集规模大时比对成功概率低能够很好的发挥作用，在字符集规模小时KMP算法更具有优势。

Karp-Rabin算法：串即是数

一个自然数向量，将其与素数序列一一对应，某个位置的数x按照顺序映射为对应素数的（x+1）次幂，然后将所有向量对应的数相乘便可得到该向量唯一对应的一个自然数，并且可以通过质因数分解将自然数还原成向量。

可惜，受寄存器字长限制，这样得到的数将特别占用存储空间。

如果将字符串都视为一个P进制的数，固然可以映射成一个数字，但是数字的长度太长，比对的效率也会很低。

Karp-Rabin算法：散列

说了这么多，无非是想表达字符串哈希的思想，先通过之前的办法将字符串映射为数，然后再将这个数通过哈希映射到有限的存储空间内。

这样，在进行串匹配时便可根据字符串对应的哈希值算法相等在常数的时间内判断在某个对其位置是否是匹配的了。

由于散列是将很大的数映射到较小的数字范围内，尽管两个串哈希值相等，但是这仅仅是必要条件，为了确保不是其它相同哈希值的串，还需要进一步遍历一次来判断是否匹配。

这里当文本串移动到下一位置时，可以去掉首字符的权值，加上新增末字符的权重来实现快速更新哈希值。

void updateHash ( HashCode& hashT, char* T, size_t m, size_t k, HashCode Dm ) {
   hashT = ( hashT - DIGIT ( T, k - 1 ) * Dm ) % M; //在前一指纹基础上，去除首位T[k - 1]
   hashT = ( hashT * R + DIGIT ( T, k + m - 1 ) ) % M; //添加末位T[k + m - 1]
   if ( 0 > hashT ) hashT += M; //确保散列码落在合法区间内
}