串的基本概念

串（也称作字符串）是由n（n≥0）个字符组成的有限序列。 

一个串中任意个连续的字符组成的子序列称为该串的子串。 包含子串的串称为该子串的主串。

一个字符在一个串中的位置序号（为大于等于0的正整数）称为该字符在串中的位置。当且仅当这两个串的值完全相等时，称这两个串相等。

串数据结构类型

数据集合：串的数据集合可以表示为字符序列s0, s1,… , sn-1，每个数据元素的数据类型为字符类型。

操作集合：

（1）取字符charAt(index) ：取index下标的字符返回。  

（2）求长度length()：返回串的长度。

（3）比较compareTo(anotherString)：比较当前对象串和串anotherString的Unicode码值的大小。 

（4）取子串substring(beginIndex, endIndex)：取当前对象串中从beginIndex下标开始、至endIndex下标的前一下标止的子串。 

（5）连接concat(str)：把串str连接到当前对象串的末尾。

（6）插入子串insert(str, pos)：在当前对象串的第pos个字符前插入子串str。

（7）删除子串delete(beginIndex, endIndex)：删除当前对象串中从beginIndex下标开始、至endIndex下标的前一下标止的子串 

（8）查找子串index(subStr, start)：在当前对象串的start下标开始，查找是否存在子串subStr。

串的存储结构

串的顺序存储结构

     串的顺序存储结构就是用字符类型数组存放串的所有字符。表示串的长度通常有两种方法：

（1）设置一个串的长度参数。

（2）在串值的末尾添加结束标记。

串值长度的第一种表示方法又可分为定长顺序存储结构和变长顺序存储结构。

定长顺序存储表示结构体定义如下：

typedef struct{  char str[maxSize+1];  int length;}

变长顺序存储表示结构体定义如下：

typedef struct{  char *str;  int length;}

 

串的链式存储结构

串的链式存储结构就是把串值分别存放在构成链表的若干个结点的数据元素域上。 有单字符结点链和块链两种。 

单字符结点链就是每个结点的数据元素域只包括一个字符。

块链就是每个结点的数据元素域包括若干个字符。

串的基本操作

#include 
    
     using namespace std;#define MaxStrSize 256typedef struct mystring{    char str[MaxStrSize];    int len;}MyString;    //求串的长度int StrLength(MyString &S){    int i=0;    while(S.str[i]!='\0')        i++;    S.len=i;    return S.len;}//打印串void StrPrint(MyString &S){    if(S.len<=0)    {       cout<<"空串!"<
     
      s.len)    {        cout<<"提取的子串过长!"<
      
       s.len)        s.len=index;    else    {        for(i=index+len;i
       
        s.len)        cout<<"插入位置不对!"<
        
         =index+t.len;i--)        {            s.str[i]=s.str[s.len-j];            j++;        }        for(i=0;i
         
          s.len ? (index+i) : s.len; s.str[s.len]='\0';}
         
        
       
      
     
    

串的匹配算法

1 串的朴素匹配算法

对主串的每一个字符作为子串开头,与要匹配的字符串进行匹配，对主串做大循环，

每个字符开头做T的长度的小循环，直到匹配成功货全部遍历完成为止。

/*检测从主串T的pos位置开始，是否有和子串S匹配,如果有返回匹配开始位置，如果没有，返回-1T:主串S:子串tlength:主串长度slength:子串长度pos:主串开始位置*/int Index (char T[],char S[],int tlength,int slength,int pos){    int j=0,i=pos;    while(i
    

2 串的KMP匹配算法

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置。

下面先直接给出 KMP 的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗花明 ☺）：

     假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置

• 如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++，继续匹配下一个字符；
• 如果 j != -1，且当前字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串 P 相对于文本串 S 向右移动了 j - next [j] 位。

      换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的 next 值（next 数组的求解会在下文中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。

很快，你也会意识到 next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如，如果 next [j] = k，代表 j 之前的字符串中有最大长度为 k 的相同前缀后缀。

此也意味着在某个字符失配时，该字符对应的 next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果 next [j] 等于 0 或 -1，则跳到模式串的开头字符，若 next [j] = k 且 k > 0，代表下次匹配跳到 j 之前的某个字符，而不是跳到开头，且具体跳过了 k 个字符。

转换成代码表示，则是：

int KmpSearch(char* s, char* p)  {      int i = 0;      int j = 0;      int sLen = strlen(s);      int pLen = strlen(p);      while (i < sLen && j < pLen)      {          //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++              if (j == -1 || s[i] == p[j])          {              i++;              j++;          }          else          {              //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]                  //next[j]即为j所对应的next值                    j = next[j];          }      }      if (j == pLen)          return i - j;      else          return -1;  }

 

寻找最长前缀后缀

如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示（前缀是说以第一个字符开始，但是不包含最后一个字符。后缀同理。）：

也就是说，原模式串子串对应的各个前缀后缀的公共元素的最大长度表为（下简称《最大长度表》）：

因为模式串中首尾可能会有重复的字符，故可得出下述结论：

失配时，模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大长度值

下面，咱们就结合之前的《最大长度表》和上述结论，进行字符串的匹配。如果给定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，现在要拿模式串去跟文本串匹配，如下图所示：

1.因为模式串中的字符 A 跟文本串中的字符 B、B、C、空格一开始就不匹配，所以不必考虑结论，直接将模式串不断的右移一位即可，直到模式串中的字符 A 跟文本串的第 5 个字符 A 匹配成功：

2.继续往后匹配，当模式串最后一个字符 D 跟文本串匹配时失配，显而易见，模式串需要向右移动。但向右移动多少位呢？因为此时已经匹配的字符数为 6 个（ABCDAB），然后根据《最大长度表》可得失配字符 D 的上一位字符B对应的长度值为 2，所以根据之前的结论，可知需要向右移动 6 - 2 = 4 位。

3.模式串向右移动 4 位后，发现 C 处再度失配，因为此时已经匹配了 2 个字符（AB），且上一位字符 B 对应的最大长度值为 0，所以向右移动：2 - 0 =2 位。

4.A 与空格失配，向右移动 1 位。

5.继续比较，发现 D 与 C 失配，故向右移动的位数为：已匹配的字符数 6 减去上一位字符 B 对应的最大长度 2，即向右移动 6 - 2 = 4 位。

6.经历第 5 步后，发现匹配成功，过程结束。

通过上述匹配过程可以看出，问题的关键就是寻找模式串中最大长度的相同前缀和后缀，找到了模式串中每个字符之前的前缀和后缀公共部分的最大长度后，便可基于此匹配。而这个最大长度便正是 next 数组要表达的含义

 

根据《最大长度表》求next数组

由上文，我们已经知道，字符串“ABCDABD”各个前缀后缀的最大公共元素长度分别为：

而且，根据这个表可以得出下述结论

• 失配时，模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大长度值

上文利用这个表和结论进行匹配时，我们发现，当匹配到一个字符失配时，其实没必要考虑当前失配的字符，更何况我们每次失配时，都是看的失配字符的上一位字符对应的最大长度值。如此，便引出了 next 数组。

给定字符串“ABCDABD”，可求得它的 next 数组如下：

把 next 数组跟之前求得的最大长度表对比后，不难发现，next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为 -1。意识到了这一点，你会惊呼原来 next 数组的求解竟然如此简单：就是找最大对称长度的前缀后缀，然后整体右移一位，初值赋为 -1（当然，你也可以直接计算某个字符对应的 next 值，就是看这个字符之前的字符串中有多大长度的相同前缀后缀）。

换言之，对于给定的模式串：ABCDABD，它的最大长度表及next 数组分别如下：

根据最大长度表求出了 next 数组后，从而有

失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值 。

递归计算next数组

1、 如果对于值 k，已有 p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于 next[j] = k。

2、 下面的问题是：已知 next [0, ..., j]，如何求出 next [j + 1] 呢？

       对于 P 的前 j+1 个序列字符：

• 若p[k] == p[j]，则 next[j + 1 ] = next [j] + 1 = k + 1；
• 若p[k ] ≠ p[j]，如果此时 p[ next[k] ] == p[j ]，则 next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引 k = next[k]，而后重复此过程。

一般的文章或教材可能就此一笔带过，但大部分的初学者可能还是不能很好的理解上述求解 next 数组的原理，故接下来，我再来着重说明下。

如下图所示，假定给定模式串 ABCDABCE，且已知 next [j] = k（即next[6]=2），现要求 next [j + 1] 等于多少？因为 pk = pj = C，所以 next[j + 1] = next[j] + 1 = k + 1（可以看出 next[j + 1] = 3）。代表字符 E 前的模式串中，有长度 k+1 的相同前缀后缀。

但如果 pk != pj 呢？

结合上图来讲，若能在前缀“ p0 pk-1 pk ” 中不断的递归前缀索引 k = next [k]，找到一个字符 pk’ 也为 D，代表 pk’ = pj，且满足 p0 pk'-1 pk' = pj-k' pj-1 pj，则最大相同的前缀后缀长度为 k' + 1.

那为何递归前缀索引k = next[k]，就能找到长度更短的相同前缀后缀呢？这又归根到 next 数组的含义。我们拿前缀 p0 pk-1 pk 去跟后缀 pj-k pj-1 pj 匹配，如果 pk 跟 pj 失配，下一步就是用 p[next[k]] 去跟 pj 继续匹配，如果 p[ next[k] ]跟 pj 还是不匹配，则需要寻找长度更短的相同前缀后缀，即下一步用 p[ next[ next[k] ] ] 去跟 pj 匹配。如下图所示：

所以在前缀ABC中经过递归并没有发现D，故E的Next值为0。

读到此，有的读者可能又有疑问了，那能否举一个能在前缀中找到字符 D 的例子呢？OK，咱们便来看一个能在前缀中找到字符 D 的例子，如下图所示：

给定模式串 DABCDABDE，我们很顺利的求得字符 D 之前的“DABCDAB”的各个子串的最长相同前缀后缀的长度分别为 0 0 0 0 1 2 3，但当遍历到字符 D，要求包括 D 在内的“DABCDABD”最长相同前缀后缀时，我们发现 pj 处的字符 D 跟 pk 处的字符 C 不一样，换言之，前缀 DABC 的最后一个字符 C 跟后缀 DABD 的最后一个字符 D 不相同，所以不存在长度为 4 的相同前缀后缀。

怎么办呢？既然没有长度为 4 的相同前缀后缀，咱们可以寻找长度短点的相同前缀后缀，最终，因在 p0 处发现也有个字符 D，p0 = pj，所以 p[j] 对应的长度值为 1，相当于 E 对应的 next 值为 1（即字符 E 之前的字符串“DABCDABD”中有长度为 1 的相同前缀和后缀）。

综上，可以通过递推求得 next 数组，代码如下所示：

void GetNext(char* p,int next[])  {      int pLen = strlen(p);      next[0] = -1;      int k = -1;      int j = 0;      while (j < pLen - 1)      {          //p[k]表示前缀，p[j]表示后缀          if (k == -1 || p[j] == p[k])           {              ++k;              ++j;              next[j] = k;          }          else           {              k = next[k];          }      }  }

 

基于 next 数组匹配

int KmpSearch(char* s, char* p)  {      int i = 0;      int j = 0;      int sLen = strlen(s);      int pLen = strlen(p);      while (i < sLen && j < pLen)      {          //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++              if (j == -1 || s[i] == p[j])          {              i++;              j++;          }          else          {              //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]                  //next[j]即为j所对应的next值                    j = next[j];          }      }      if (j == pLen)          return i - j;      else          return -1;  }

 

 

脑子不够用了。。今天先到这。。

 

 

参考：