串基础

顺序存储

定长数组存储：将实际的串长存放在数组的第 0 个位置或是使用“0”作为终结符。

但是串是的顺序存储存在一个潜在的风险——溢出问题。

所以，串的存储空间可以动态的分配。

链式存储

类似链表，但是并不是一个链块只存放一个字符，而是多个。若是没有占满的话可以使用“#”来结束。

其实链式存储只是在串的连接与串操作时有一定优势，总体来说不然顺序存储。

串操作 Code

// 头文件
//kallen 1 #ifndef _HSTRING_H_
 2 #define _HSTRING_H_
 3 #include <iostream>
 4 class mString
 5 {
 6 public:
 7     mString();
 8     void newString(const char *ms);
 9     ~mString();
10     bool isEmpty()const;          
11     int  lengthString()const;     
12     void copyString(const mString &src); 
13     friend int compareString(const mString &lhs,const mString &rhs); 
14     void clearStirng();  
15     void concatString(const mString &lhs_src,const mString &rhs_src); 
16     void subString(const mString &src,int pos,int len);      
17     void insertString(int pos,const mString &ms); 
18     void deleteString(int pos,int len);
19     int  indexkfString(const mString &mt,int pos);
20     int  indexkmpString(const mString &mt,int pos,int *next);                                           
21     void replaceString(int repos,const mString& mt,const mString &mv,int *next);  
22     
23     void insaftposString(int pps,const mString& mt,const mString& mv);
24     void printString()const;
25 private:
26     char *base;
27     int  length;
28     void nextSt(const mString& mt,int *next);
29 };
30 
31 #endif //_HSTRING_H_

// 实现文件
#include "hstring.h"

mString::mString()
{
    base = NULL;
    length = 0;
}

mString::~mString()
{if (base!=NULL)
    {delete base;}
    base = NULL;
}

void mString::newString(const char *ms)
{
    int i = 0;
    while(ms[i]!='\0')
    {++i;}
    length = i;
    base = new char[length + 1];
    for (int j = 0;j<length;++j)
    {base[j] = ms[j];
    }
    base[length] = '\0';
}

bool mString::isEmpty()const
{if (0 == length)
    {return true;}
    else
    {return false;}
}

int mString::lengthString()const
{return length;}

void mString::copyString(const mString &src)
{
    int i = 0;
    for (; i<this->length;++i)
    {base[i] = src.base[i];
    }
}

int compareString(const mString &lhs,const mString &rhs)
{
    int i = 0;
    while (lhs.base[i]!='\0'&&lhs.base[i]!='\0')
    {if (lhs.base[i] > rhs.base[i])
        {return 1;}
        else if (lhs.base[i] < rhs.base[i])
        {return -1;}
        else
        {++i;}
    }
    if (lhs.base[i] =='\0'&&rhs.base[i]!='\0')
    {return -1;}
    else if (lhs.base[i] !='\0'&&rhs.base[i]=='\0')
    {return 1;}
    else
    {return 0;}
}

void mString::clearStirng()
{length = 0;}

void mString::concatString(const mString &lhs_src,const mString &rhs_src)
{

    length = lhs_src.length + rhs_src.length;
    this->base = new char[length+1];

    for (int i = 0; i<lhs_src.length; ++i)
    {this->base[i] = lhs_src.base[i];
    }
    for (int i = lhs_src.length,j = 0; j < rhs_src.length; ++j,++i)
    {this->base[i] = rhs_src.base[j];
    }
    this->base[length] = '\0';

}

void mString::printString()const
{
    int i = 0;
    for (;i<length;++i)
    {std::cout<<base[i];
    }
    std::cout<<std::endl;
}

void mString::subString(const mString &src,int pos,int len)
{if (src.length != 0)
    {if (pos>src.length)
        {std::cout<<"The  location of pos is illegal!"<<std::endl;}
        else
        {if (pos+len-1 <=src.length)
            {
                length = len;
                this->base = new char[length+1];

                for(int i = 0; i < length; ++i,++pos)
                {this->base[i] = src.base[pos-1];
                }
            }
            else
            {
                length = src.length-pos+1;
                this->base = new char[length+1];
                int j = 0;
                for (;j<length;++j,++pos)
                {this->base[j] = src.base[pos-1];
                }
                this->base[j] = '\0';
            }
        }

    }
    else
    {std::cout<<"The string is empty!"<<std::endl;}
}

void mString::deleteString(int pos,int len)
{if (0 == length)
    {std::cout<<"The string is empty!"<<std::endl;}
    else
    {if (pos>length)
        {std::cout<<"The location of pos is illegal!"<<std::endl;}
        else
        {if (pos+len-1>=length) //delete all char after pos,
                                   //but it don't move any char
            {
                int i = pos - 1;
                for (;i<length;++i)
                {base[i] = '\0';
                }
            }
            else                   //pos+len-1<length,we have to move the char that
                                   //from pos+len to length
            {int i = pos-1,j=pos+len-1,k=length-(pos+len)+1;
                for (;k>0;--k,++i,++j)
                {base[i] = base[j];
                }
                for (int m = len,n = length;m>0;--n,--m)
                {base[n-1] = '\0';
                }
            }
        }

    }
}

void mString::insertString(int pos,const mString &ms)//insert ms before pos
{if (0!=length&&0!=ms.length)
    {if (pos>length)
        {std::cout<<"The location of pos is illegal!"<<std::endl;}
        else
        {
            int len = ms.length,i = length-1,j=length+len-1,k = length-pos+1;
            int m = pos,n=0;
            base = (char *)realloc(base,(length+len)*sizeof(char));
            length = length+len;
            if (base==NULL)
            {std::cout<<"Create memory is failed!"<<std::endl;}
            for (;k>0;--k,--i,--j)
            {base[j] = base[i];
            }
            base[length]='\0';
            for (;n<len;++m,++n)
            {base[m-1] = ms.base[n];
            }
        }
    }
    else
    {std::cout<<"The string is empty!"<<std::endl;}
}

int  mString::indexkfString(const mString &mt,int pos)
{if (length != 0 &&mt.length!=0)
    {if (pos>length-mt.length+1)
        {
            std::cout<<"The location of pos is illegal!"<<std::endl;
            return 0;
        }
        else
        {
            int i = 1,j = pos;
            while(i<=mt.length&&j<=length)
            {if (mt.base[i-1]==base[j-1])
                {
                    ++i;
                    ++j;
                }
                else
                {
                    j = j-i+2;
                    i = 1;            //it's wrong if example : i = 1; j =j-i+2;
                    if (j>length-mt.length +1)
                    {break;}
                }
            }
            if (i > mt.length)
            {return (j-i+1);
            }
            else
            {return 0;}
        }
    }
    else
    {
        std::cout<<"The string is empty!"<<std::endl;
        return 0;
    }
}

int  mString::indexkmpString(const mString &mt,int pos,int *next)
{
    int i = pos,j = 0;
    nextSt(mt,next);
    while(j<mt.length&&i<=length)
    {if (j == -1||mt.base[j]==base[i-1])
        {
            ++i;
            ++j;
        }
        else
        {j = next[j];
        }
    }
    if (j==mt.length)
    {
        std::cout<<i-j<<std::endl;
        return (i - j);
    }
    else
    {
        std::cout<<"nothing"<<std::endl;
        return 0;
    }
}

void mString::nextSt(const mString& mt,int *next)
{
    int i = 0,j = -1;
    next[0] = -1;
    while (i<mt.length)
    {if (j==-1||mt.base[i]==mt.base[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {j = next[j];
        }
    }
    //for (int i = 0;i<mt.length;++i)
    //{//std::cout<<next[i];
    //}
}

void mString::replaceString(int repos,const mString& mt,const mString &mv,int *next)
{if (length!=0)
    {
        int pos = repos;
        if (mt.length!=0&&mv.length!=0)
        {
            int pps = pos;
            while(pos!=0)
            {pos = indexkmpString(mt,pps,next);
                if (pos!=0)                              //when pos == 0,maybe execute copy in the head
                {                                        //example;a = "abcaabcacbc";mt = "bc";mv = "ff";
                    insaftposString(pos,mt,mv);          //but the result is; "fffaaffacff".
                }
                pps = pos+mv.length;            //from  pos+mv.length
            }
        }
        else
        {std::cout<<"The string of mt or mv  is empty!"<<std::endl;}

    }
    else
    {std::cout<<"The main string is empty!"<<std::endl;}

}

void mString::insaftposString(int pps,const mString& mt,const mString& mv)
{if (mt.length<mv.length)
    {int n   = length - (pps+mt.length-1);       //the sum of movement
        int dis = mv.length - mt.length;
        int k   = length+dis-1;
        int j   = length-1;
        base = (char *)realloc(base,(length+dis)*sizeof(char));
        length = length+dis;
        if (base==NULL)
        {std::cout<<"Create memory is failed!"<<std::endl;}
        for (int i = 1;i<=n;++i,--k,--j)
        {base[k] = base[j];
        }
        base[length] = '\0';
        for (int i = 0,j=pps-1;i<mv.length;++i,++j)
        {base[j] = mv.base[i];
        }
    }
    else if (mt.length>mv.length)
    {int n = length - (pps+mt.length-1);
        int dis = mt.length-mv.length;
        int i = pps+mv.length-1;
        int j = pps+mt.length-1;
        for (int k = pps-1,l = 0;l<mv.length;++l,++k)
        {base[k] = mv.base[l];
        }
        for (int k=1;k<=n;++k,++i,++j)
        {base[i]=base[j];
        }
        for (int k=1,l = length-1;k<=dis;++k)
        {base[l] = '\0';
        }
        length = length-dis;
    }
    else
    {for (int i = 0;i<mv.length;++i,++pps)
        {base[pps-1] = mv.base[i];
        }
        printString();//inserts without thinks}

}

串的算符重载

//Sting.h
#ifndef _STRING_H_
#define _STRING_H_
#include <iostream>
using namespace std;

class String
{
public:
    String(const char *str = "");
    String(const String &other);
    String &operator=(const String &other);
    String &operator=(const char *str);

    bool operator!() const;
    char &operator[](unsigned int index);
    const char &operator[](unsigned int index) const;

    friend String operator+(const String &s1, const String &s2);
    String &operator+=(const String &other);

    friend ostream &operator<<(ostream &os, const String &str);
    friend istream &operator>>(istream &is, String &str);
    ~String(void);

    void Display() const;
    int Length() const;
    bool IsEmpty() const;

private:
    String &Assign(const char *str);
    char *AllocAndCpy(const char *str);
    char *str_;
};

#endif // _STRING_H_

//String.cpp
#pragma warning(disable:4996)
#include "String.h"
#include <string.h>
//#include <iostream>
//using namespace std;

String::String(const char *str)
{str_ = AllocAndCpy(str);
}

String::String(const String &other)
{str_ = AllocAndCpy(other.str_);
}

String &String::operator=(const String &other)
{if (this == &other)
        return *this;

    return Assign(other.str_);
}

String &String::operator=(const char *str)
{return Assign(str);
}

String &String::Assign(const char *str)
{delete[] str_;
    str_ = AllocAndCpy(str);
    return *this;
}

bool String::operator!() const
{return strlen(str_) != 0;
}

char &String::operator[](unsigned int index)
{//return str_[index];
    //non const 版本调用 const 版本

    return const_cast<char &>(static_cast<const String &>(*this)[index]);
}

const char &String::operator[](unsigned int index) const
{return str_[index];
}

String::~String()
{delete[] str_;
}

char *String::AllocAndCpy(const char *str)
{int len = strlen(str) + 1;
    char *newstr = new char[len];
    memset(newstr, 0, len);
    strcpy(newstr, str);

    return newstr;
}

void String::Display() const
{cout << str_ << endl;}

int String::Length() const
{return strlen(str_);
}

bool String::IsEmpty() const
{return Length() == 0;
}

String operator+(const String &s1, const String &s2)
{//int len = strlen(s1.str_) + strlen(s2.str_) + 1;
    //char* newstr = new char[len];
    //memset(newstr, 0, len);
    //strcpy(newstr, s1.str_);
    //strcat(newstr, s2.str_);
    //
    //String tmp(newstr);
    //delete newstr;
    String str = s1;
    str += s2;
    return str;
}

String &String::operator+=(const String &other)
{int len = strlen(str_) + strlen(other.str_) + 1;
    char *newstr = new char[len];
    memset(newstr, 0, len);
    strcpy(newstr, str_);
    strcat(newstr, other.str_);

    delete[] str_;

    str_ = newstr;
    return *this;
}

ostream &operator<<(ostream &os, const String &str)
{
    os << str.str_;
    return os;
}

istream &operator>>(istream &is, String &str)
{char tmp[1024];
    cin >> tmp;
    str = tmp;
    return is;
}

串的匹配

朴素串匹配（BF 算法）

朴素串匹配算法的思路是暴力求解。一个一个的找。一旦不匹配就会全退回去。

Code

int Index(sting s, string t, int pos){
    int i = pos;
    int j = 1;
    while(i <= s[0] && j <= t[0]){if(s[i] == t[j]){++i;++j;}else{
            i = i - j + 2;
            j = 1;
        }
    }
    if(j > t[0]){return i - t[0];
    }else{return 0;}
}

KMP 算法

思路

寻找最大公共前后缀，不匹配之后直接从前缀移到后缀处。

怎么求最大公共前后缀呢？

​ 如果想增加最长公共前后缀长度增加的话，当且仅当 在最后再添加一个字符。

Next 数组中第一个元素为 -1，第二个元素代表 由 0 1 两个字符构成的字符串的最大公共前后缀的长度，第三个元素和之后的元素类推….

若第二个元素为 0，如果想让第三个元素+1，则后面必须接字符串的第三个字符

A B ——0

A B A——1

A B A B——2

A B A B C——0

即，Next 数组的后一个是与前一个有关系的：如果我想知道 Next[x]是多少，则我只需要看 Next[x-1]对应的字符串最大前后缀 后一个字符即可。如果 Next[x]对应的字符串最后一个字符和 Next[x-1]最大公共前缀的后一个字符一样，则可以 +1，否则为 0.(注意！这里的 0 并不是随便的写的，如果这个位置是最后一格位置，很有可能不是 0。此时我们 len-1，然后将 len 移到 Next[len-1]的位置，即 len = Next[len-1])

具体我们使用 len 保存最大公共前后缀的长度。即 P[len]==P[i]；len++；Next[i] = len;

Code

#include <stdio.h>
void prefix_table(char pattern[], int prefix[], int n){prefix[0] = 0;// 第一位永远为 0, 规定
    int len = 0;
    int i = 1;
    while(i < n){if(pattern[i] == pattern[len]){
            len++;
            prefix[i] = len;
            i++;
        }else{if(len > 0){len = prefix[len - 1];   // 不停的往左对，要注意数组越界的问题
            }else{prefix[i] = len;//len 是 0
                i++;
            }                   
        }
    }
}
// 我们默认将 prefix 整体向后移位，然后第一个位置填写 -1
void move_prefix_table(int prefix[], int n){
    int i ;
    for(i = n - 1; i > 0; i--){prefix[i] = i - 1;    
    }
    prefix[0] = -1
}

void kmp_search(char text[], char pattern[]){\
    int n = strlen(pattern);
    int m = strlen(text);
    int * prefix = malloc(sizeof(int) * n);
    prefix_table(pattern, prefix, n);
    move_prefix_table(prefix, n);
    //text[i]       len(text) = m
    //pattern[j]    len(pattern) = n
    i = 0;
    j = 0;
                                          
    while(i < m){if(j == n - 1 && text[i] == pattern[j]){printf("Found pattern at %d\n", i - j);
            j = prefix[j];
        }
        if(text[i] == pattern[j]){i++;j++}else{j = prefix[x];
            if(j == -1){i++;j++;}
        }
    }
}
int main(){char pattern[] = "ABABCABAA";
    char text[] = "ABABABCABAAABASBA";
    kmp_search(text, pattern)
    int prefix[9];
    int n = 9;
    prefix_table(pattern,prefix,n);
    move_prefix_table(prefix, n);
    
    int i;
    for(i = 0; i < n; i++){printf("%d\n",prefix[i]);
    }
    return 0;
}

BM 算法

来源：https://www.cnblogs.com/wxgbl…

详情参考 邓俊辉 ——《数据结构 C ++ 版》，清华大学出版社

参考：
http://www-igm.univ-mlv.fr/~l…

http://www.cs.utexas.edu/user…

后缀匹配，是指模式串的比较从右到左，模式串的移动也是从左到右的匹配过程，经典的 BM 算法其实是对后缀蛮力匹配算法的改进。为了实现更快移动模式串，BM 算法定义了两个规则，好后缀规则和坏字符规则，如下图可以清晰的看出他们的含义。利用好后缀和坏字符可以大大加快模式串的移动距离，不是简单的 ++j，而是 j +=max (shift(好后缀), shift(坏字符))

先来看如何根据坏字符来移动模式串，shift(坏字符)分为两种情况：

• 坏字符没出现在模式串中，这时可以把模式串移动到坏字符的下一个字符，继续比较，如下图：

• 坏字符出现在模式串中，这时可以把模式串第一个出现的坏字符和母串的坏字符对齐，当然，这样可能造成模式串倒退移动，如下图：

此处配的图是不准确的，因为显然加粗的那个 b 并不是”最 靠右的”b。而且也与下面给出的代码冲突！我看了论文，论文的意思是最右边的。当然了，尽管一时大意图配错了，论述还是没有问题的，我们可以把图改正一 下，把圈圈中的 b 改为字母 f 就好了。接下来的图就不再更改了，大家心里有数就好。
为了用代码来描述上述的两种情况，设计一个数组 bmBc[‘k’]，表示坏字符‘k’在模式串中出现的位置距离模式串末尾的最大长度，那么当遇到坏字符的时候，模式串可以移动距离为：shift(坏字符) = bmBc[T[i]]-（m-1-i)。如下图：

数组 bmBc 的创建非常简单，直接贴出代码如下：

void preBmBc(char *x, int m, int bmBc[]) {

   int i;

   for (i = 0; i < ASIZE; ++i)

      bmBc[i] = m;

   for (i = 0; i <= m - 1; ++i)

      bmBc[x[i]] = m - i - 1;

}

代码分析：

• ASIZE 是指字符种类个数，为了方便起见，就直接把 ASCII 表中的 256 个字符全表示了，哈哈，这样就不会漏掉哪个字符了。
• 第一个 for 循环处理上述的第一种情况，这种情况比较容易理解就不多提了。第二个 for 循环，bmBc[x[i]]中 x[i]表示模式串中的第 i 个字符。bmBc[x[i]] = m – i – 1; 也就是计算 x[i]这个字符到串尾部的距离。
• 为什么第二个 for 循环中，i 从小到大的顺序计算呢？哈哈，技巧就在这儿了，原因在于就可以在同一字符多次出现的时候以最靠右的那个字符到尾部距离为最终的距离。当然了，如果没在模式串中出现的字符，其距离就是 m 了。

再来看如何根据好后缀规则移动模式串，shift（好后缀）分为三种情况：

• 模式串中有子串匹配上好后缀，此时移动模式串，让该子串和好后缀对齐即可，如果超过一个子串匹配上好后缀，则选择最靠左边的子串对齐。

• 模式串中没有子串匹配上后后缀，此时需要寻找模式串的一个最长前缀，并让该前缀等于好后缀的后缀，寻找到该前缀后，让该前缀和好后缀对齐即可。

• 模式串中没有子串匹配上后后缀，并且在模式串中找不到最长前缀，让该前缀等于好后缀的后缀。此时，直接移动模式到好后缀的下一个字符。

为了实现好后缀规则，需要定义一个数组 suffix[]，其中 suffix[i] = s 表示以 i 为边界，与模式串后缀匹配的最大长度，如下图所示，用公式可以描述：满足 P[i-s, i] == P[m-s, m]的最大长度 s。

构建 suffix 数组的代码如下：

void suffixes(char *x, int m, int *suff)
 {suff[m-1]=m;
  for (i=m-2；i>=0；--i){
    q=i;
    while(q>=0&&x[q]==x[m-1-i+q])
        --q;
    suff[i]=i-q;
}
}

·注解：这一部分代码乏善可陈，都是常规代码，这里就不多说了。

有了 suffix 数组，就可以定义 bmGs[]数组，bmGs[i] 表示遇到好后缀时，模式串应该移动的距离，其中 i 表示好后缀前面一个字符的位置（也就是坏字符的位置），构建 bmGs 数组分为三种情况，分别对应上述的移动模式串的三种情况

• 模式串中有子串匹配上好后缀

• 模式串中没有子串匹配上好后缀，但找到一个最大前缀

• 模式串中没有子串匹配上好后缀，但找不到一个最大前缀

构建 bmGs 数组的代码如下：

void preBmGs(char *x, int m, int bmGs[]) {int i, j, suff[XSIZE];
   suffixes(x, m, suff);
   for (i = 0; i < m; ++i)
      bmGs[i] = m;
   j = 0;
   for (i = m - 1; i >= 0; --i)
      if (suff[i] == i + 1)
         for (; j < m - 1 - i; ++j)
            if (bmGs[j] == m)
               bmGs[j] = m - 1 - i;
   for (i = 0; i <= m - 2; ++i)
      bmGs[m - 1 - suff[i]] = m - 1 - i;
}

注解：这一部分代码挺有讲究，写的很巧妙，这里谈谈我的理解。讲解代码时候是分为三种情况来说明的，其实第二种和第三种可以合并，因为第三种情况相当于与好后缀匹配的最长前缀长度为 0。由于我们的目的是获得精确的 bmGs[i]，故而若一个 字符同时符合上述三种情况中的几种，那么我们选取最小的 bmGs[i]。比如当模式传中既有子串可以匹配上好后串，又有前缀可以匹配好后串的后串，那么此 时我们应该按照前者来移动模式串，也就是 bmGs[i]较小的那种情况。故而每次修改 bmGs[i]都应该使其变小，记住这一点，很重要！而在这三种情况中第三种情况获得的 bmGs[i]值大于第二种大于第一种。故而写代码的时候我们先计算第三种情况，再计算第二种情况，再计算第一种情况。为什么呢，因为对于同一个位置的多次修改只会使得 bmGs[i]越来越小。

• 代码 4 - 5 行对应了第三种情况，7-11 行对于第二种情况，12-13 对应第三种情况。
• 第三种情况比较简单直接赋值 m，这里就不多提了。
• 第二种情况有点意思，咱们细细的来品味一下。

1. 为什么从后往前，也就是 i 从大到小？原因在于如果 i,j(i>j)位置同时满足第二种情况，那么 m -1-i<m-1-j，而第十行代码保证了每个位置最多只能被修改一次，故而应该赋值为 m -1-i，这也说明了为什么要从后往前计算。

2. 第 8 行代码的意思是找到了合适的位置，为什么这么说呢？因为根据 suff 的定义，我们知道 x[i+1-suff[i]…i]==x[m-1-siff[i]…m-1], 而 suff[i]==i+1，我们知道 x[i+1-suff[i]…i]=x[0,i], 也就是前缀，满足第二种情况。

​ 3. 第 9 -11 行就是在对满足第二种情况下的赋值了。第十行确保了每个位置最多只能被修改一次。

• 第 12-13 行就是处理第一种情况了。为什么顺序从前到后呢，也就是 i 从小到大？原因在于如果 suff[i]==suff[j]，i<j，那么 m -1-i>m-1-j, 我们应该取后者作为 bmGs[m – 1 – suff[i]]的值。

Code

void BM(char *x, int m, char *y, int n) {int i, j, bmGs[XSIZE], bmBc[ASIZE];

   /* Preprocessing */
   preBmGs(x, m, bmGs);
   preBmBc(x, m, bmBc);

   /* Searching */
   j = 0;
   while (j <= n - m) {for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
      if (i < 0) {OUTPUT(j);
         j += bmGs[0];
      }
      else
         j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
   }
}

Karp-Rabin 算法

来源：https://blog.csdn.net/Shine__…

选自：邓俊辉——《数据结构 C ++ 版》，清华大学出版社

万物皆数

回想我们平时对整数进行的比较，都可以在 O(1)的时间内完成，而任何数据在计算机中的存储都是一系列的字节构成的二进制整数，串也不例外，那为什么不可以把对整数高效的比较操作也移植到串匹配问题上呢？这就是 karp-rabin 的基本思想。

一般地，对于任意一个串，设字符集的大小为 d，则该串中的任意一个字符都可以用一个 d + 1 进制的整数来表示。需要注意的是，这里是 d + 1 进制，而不是 d 进制，是因为不能用 0 来表示任意一个字符，否则如果该字符组成串的一个前缀，无论前缀的长度多少，都不会影响串所对应的整数取值。

在这种情况下，任意一个串，都可以将之用整数表示出来，并且串与这个整数是唯一对应的，因此这是一个完美散列，因此将该整数称为串的指纹(fingerprint)。如果将该指纹转化为二进制整数，就可以在计算机中用二进制字节流唯一地表示一个字符串了。

karp-rabin 算法

根据上面的分析似乎已经可以构造出一个新的串匹配算法了，具体说来，在每一个对齐位置，将模式串和与之对齐的文本串的 m 个字符，分别用其指纹表示出来，然后利用整数的比较就可以在 O(1)时间内完成匹配，这样整体的时间复杂度为 O(n)，已经和 kmp 算法相当了！可是，果真这么简单吗？

答案是否定的，因为该过程中还存在着其他开销——比如将长度为 m 的串转化为其对应的指纹，其开销就已经是 O(m)了，因此整个算法的时间开销是 O(mn)，与蛮力策略相当！此外，还存在一些新的问题，当字符集较大，或者串长度较长时，其转化成的指纹位数也会相当长，比如采用 ASCII 码字符集时，字符集的大小 d = 128，如果模式串的长度 m = 10，则其对应的指纹会占 7 x 10 = 70 个比特，已经超过了计算机中通常支持的整数位数，并且随着串的进一步增长，对这么多位指纹的比对也难以在 O(1)时间内完成，而是也要消耗 O(m)的时间，同时对这些整数的存储也是一个问题。

下面就从各个方面分别讨论怎么解决上述存在的这么多问题。

指纹长度的压缩

将更大的数据，存储到更小的空间，这其实是我们在散列的基本概念中就提出过的问题。具体说来，为了将 70bits 乃至更长的指纹压缩到 32bit 整数表示的范围内，只需要对该指纹做一个散列，不妨就简明地采用模余法，即

hash(fingerprint) = fingerprint % M;

这样，就一次性地解决了整数的存储与比对时间的问题，经过散列后的指纹可以存储在计算机通常支持的位长度以内，并且此时对指纹的比对又只需要 O(1)的时间了。

但是由于散列内在的缺陷，不可避免地又会引入新的问题——冲突。对于两个不相匹配的串，它们经过压缩后的指纹却有可能相同，此时就会导致误判。为了解决这个问题，可以使指纹相同作为串匹配的必要条件，一旦发现两个串的指纹相同，可以对它们再启动一次逐个比较的字符比对，来确定这两个串是否的确是匹配的。需要指出，只要这里的散列长度足够长，就可以保证一般情况下两个不匹配的串，其指纹相同的概率极低，从而引入的逐个字符比对并不会显著地增加算法的时间复杂度。

快速指纹更新

尽管在引入了散列以后，指纹的比对可以在 O(1)时间内完成了，但是指纹的计算仍然需要 O(m)的时间，此时 karp-rabin 算法整体的时间复杂度仍然是 O(mn)，没有显著的提高，因此需要提供一种快速的指纹计算方法。

对于模式串而言，指纹的计算是没有办法提高了，因为 m 个字符肯定需要全部遍历一次才能计算出它对应的指纹，O(m)的时间复杂度没有任何可以提高的空间。

但是对于文本串则不然，诚然，对于任意一个长度为 m 的串，计算其指纹也必须需要 O(m)的时间开销，但是在文本串中，可以注意到，相邻串的指纹是具有一定的联系的，如下图所示：

具体说来，相邻串只有最前一个字符和最后一个字符是不相同的，利用模余的运算法则，就可以根据前一个串的指纹，在 O(1)时间内计算出下一个串的指纹。设 a, b 分别是两个正整数，且有 a > b > 0，具体利用到的运算法则是，

(a + b) % M = ((a % M) + (b % M)) % M = ((a % M) + b) % M = ((b % M) + a) % M;
(a - b) % M = ((a % M) - (b % M) + M) % M;
(a * b) % M = ((a % M) * (b % M)) % M;

上述的运算法则均可以推广到多个正整数的情形。因此，就可以构造出计算模式串和文本串的初始指纹的代码：

m = strlen(P);
HashCode hashP = 0, hashT = 0;
for(int i = 0; i < m; ++i){hashP = (hashP * R + DIGIT(P, i)) % M;
    hashT = (hashT * R + DIGIT(T, i)) % M;
}

为了快速更新文本串相邻长度为 m 的子串的指纹，需要首先从原先的指纹中，减去最高位的部分，再加上最低位的部分，而计算最高位字符的模余值，需要做 m – 1 次连乘运算，即

fingerprint(P[0]) = P[0] * R^(m - 1)

为了简化这个运算，可以事先将 R^(m – 1)计算并保存，形成下面的代码：

HashCode prepareDm(int m){
    HashCode Dm = 1;
    for(int i = 0; i != m; ++i)
        Dm = (Dm * R) % M;
    return Dm;
}

可以注意到，上面计算得出的 Dm，正是 R^(m – 1)的模余值，这里是利用到了模余的第三条运算法则。所以可以形成下面的快速更新指纹的代码：

void updateHash(HashCode &hashT, char* T, int m, int k, HashCode Dm){hashT = (hashT - DIGIT(T, k - 1) * Dm + M) % M;
    hashT = (hashT * R + DIGIT(T, k - 1 + m)) % M;
}

该算法其实就是上面三条模余运算法则的反复使用。

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int char_to_int(char c) {return c - '0';}
 
int module(int x, int q) {if (x < 0) {return x % q + q;}
    else {return x % q;}
}
 
bool is_forge(char* P1, char* P2, int m) {for (int i = 0; i < m; ++i) {if (P1[i] != P2[i]) {return true;}
    }
    return false;
}
 
void rabin_karp(char* T, char* P, int d, int q, int m, int n) {int x = pow(d, m - 1);
    int h = module(x, q);
    int p{};
    int* t = new int[n - m] {};
    for (int i = 0; i < m; ++i) {p = module(d * p + char_to_int(P[i]), q);
        t[0] = module(d * t[0] + char_to_int(T[i]), q);
    }
    for (int s = 0; s < n - m - 1; ++s) {if (p == t[s]) {if (!is_forge(P, T + s, m)) {cout << "Pattern occurs with shift" << s - 1 << endl;}
        }
        else {t[s + 1] = module(d * (t[s] - char_to_int(T[s]) * h) + char_to_int(T[s + m]), q);
        }
    }
    delete[]t;}
 
 
int main(int argc, char* argv[]) {vector<char> v{};
    int d{10};
    cout << "please enter the radix :" << endl;
    cin >> d;
    int q{};
    cout << "please enter the mod number (prime better) :" << endl;
    cin >> q;
    char element{};
    cout << "please enter the pattern (end with'a') :" << endl;
    while (cin >> element) {if (element != 'a') {v.push_back(element);
        }
        else {break;}
    }
    int m = v.size();
    char* P = new char[m] {};
    int index{};
    for_each(v.begin(), v.end(), [=](char x)mutable{P[index++] = x; });
    v.clear();
    cout << "please enter the text (end with'a') :" << endl;
    while (cin >> element) {if (element != 'a') {v.push_back(element);
        }
        else {break;}
    }
    int n = v.size();
    char* T = new char[n] {};
    index = 0;
    for_each(v.begin(), v.end(), [=](char x)mutable{T[index++] = x; });
    rabin_karp(T, P, d, q, m, n);
    delete[]T;
    delete[]P;
    return 0;
}

点更深入讨论

来源：https://blog.csdn.net/lucylov…

基本思想和暴力破解算法是一样的。也需要一个大小为 m 的窗口，但是不一样的是，不是直接比较两个长度为 m 的字符串，而是比较他们的哈希值。

同样的，现在我们做他们的复杂度分析，in worst case，一共会有 (n-m+1) 个窗口滑动。-> 这一步的复杂度是 O(n)

这个是不变的，但是由于哈希值都是数字，所以两个数字的比较，只需要 O(1)。

但是计算哈希值的时间呢？

在一开始的时候，我们需要计算 p 的哈希值，由于 p 的长度为 m，所以计算 p 的哈希值的时间为 O(m).

然后每一次移动窗口，都需要对窗口内的字符串计算哈希值，此时这个字符串的长度为 m，所以计算它哈希值的时间也为 O(m). 如果照这样看，算法复杂度还是 O(m*n)，和上面的暴力破解算法没有任何区别。

但是实际上，计算移动窗口内的哈希值并不需要 O(m)，在已知前一个窗口的哈希值的情况下，计算当前窗口的哈希值，只需要 O(1)的时间复杂度。

现在再来看上面提到的计算字符串哈希值的函数，假设现在窗口的起点在 j 这个位置，此时窗口内的字符串哈希值为：

​

那么，当计算下一个窗口的哈希值时，也就是当窗口的起点为 j + 1 时，哈希函数值可由如下方法计算：

​

所以，这样看来，在计算出第一个窗口的函数值之后，后面的每一个窗口哈希值都可以根据上述公式计算，只需要做一次减法，一次乘法，一次加法。所以之后的每一次哈希值计算都是 O(1)的复杂度。

那么重头来算一次复杂度：

一共有 (n-m+1) 个窗口，复杂度为 O(n).

计算 p 的哈希值 O(m)，计算第一个窗口的复杂度，O(m).

此后计算每一个窗口的复杂度 O(1).

所以最终的复杂度是 O(m+n)。