串

定义：零个或多个字符组成的有限序列

衍生定义：

子串：串中任意个连续的字符组成的子序列称为该串的子串。
主串：包含子串的串称为主串
串相等：两个串长度相等，且对应位置的字符都相等
空格串/空白串：由一个或多个空格组成
空串：空串不包含任何字符，长度为0。

串的顺序存储结构

定长顺序存储表示

存储定义：

#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1];

在SString[0]处存放字符串的长度

约定：串值长度上溢时，用“截尾法”处理，即“截断”超过予定义长度的部分。

StrCompare()

int StrCompare(SString S, SString T)
//S>T,返回值>0；S=T，返回0；S<T，返回值< 0
{   
    for(i=1; i<=S[0] && i<=T[0];  i++)
        if( S[i] != T[i] )
            return(S[i] - T[i] );
    return S[0]-T[0]
}

Concat

bool Concat(SString  &T,  SString S1, SString S2)
//用T返回串s1和s2联接而成的新串。
//若未截断，返回TRUE，否则返回FALSE
{   
    if( S1[0]+S2[0] <= MAXSTRLEN ) {
		     T[1..S1[0]] = S1[1..S1[0]];
		     T[s1[0]+1..S1[0]+S2[0]] = S2[1..S2[0]];
		     T[0]= S1[0]+S2[0];  uncut=TRUE;
    }
    else if  (S1[0]<MAXSTRLEN) {
        T[1..S1[0]] = S1[1..S1[0]];
		     T[s1[0]+1..MAXSTRLEN] = S2[1..MAXSTRLEN-S1[0]];
		     T[0]= MAXSTRLEN;  uncut=FALSE;
    }
    else  {
        T[0..MAXSTRLEN]= S1[0..MAXSTRLEN];  
        uncut= FALSE;
    }
    return uncut;
} // Concat

SubString

Status SubString(SString &Sub, SString S, int pos, int len)
//用Sub返回串S从第pos个字符起长度为len的子串
//隐含的意思：sub空间必须大于等于len+1
{  
    if( pos<1 || pos>S[0]  || len<0  || len>S[0]-pos+1 )
        return ERROR;
    Sub[1..len]= S[pos..pos+len-1];
	  Sub[0]= len;
	  return OK;
} // SubString

堆分配存储表示

代码定义：

typedef struct{
	char *ch;	//按串长分配存储区，ch指向串的基地址
	int length;	//串的长度
}HString;

动态分配串值存储空间，避免定长结构的截断现象。

串的块链存储结构

串的块链存储结构通过链表来实现，不过在链表中存贮时，一个节点既可以只存储一个字符也可以存储多个字符，每个节点称为块，通过改变尾指针，在进行连接操作时很方便，但是其他操作很不方便，且占用储存大，很少应用。

代码定义：

#define CHUNKSIZE  4           //由用户定义块大小
typedef  struct  Chunk  {
         char  ch[CHUNKSIZE];
         struct Chunk * next;
}Chunk; //中间节点

typedef  struct  {   //头尾指针的单链表，结点的data是字符块
    Chunk * head， * tail;    //串的、尾头指针
    int    curlen;           //串的当前长度
}LString; //头节点

BF匹配算法

先导：在这一节中，我们将需要寻找的字符串叫做模式串，即我们需要在主串中寻找是否由模式串存在。

暴力穷举法，从主串的第0个字符开始比较，用i跟踪，和匹配字符串的第一个字符（用j跟踪）比较，若相等，则继续比较后续的字符；若不等，从主串的下一字符起，从主串的下一字符起(i=i-j+2)，重新与模式的第一个字符(j=1)比较。直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值 0。否则，匹配失败，返回值 0

代码实现如下：

bool Index(char* s,char* p,int * pos)
{
    for(int i = 0;s[i] != '\0';i++)
    {
        int j = 0,ti = i;
        if(s[ti] == p[j])
        {
            while(p[j] != '\0' && s[ti] != '\0' && p[j] == s[ti])
            {
                ti++,j++;
            }
            if(p[j] == '\0')
            {
                *pos = i;
                return true;
            }
        }
    }
    return false;
}

BF算法的时间复杂度为最好情况为O(n*m)。所以我们来了解一种效率更高的匹配算法。

KMP算法

想要更好的理解KMP算法，我们需要先引入KMP算法中的next数组概念

next数组

next数组的长度与模式串相等，其中存放的数据类型为整型。我们先举个例子来看一下什么是next串。

位置  ：0 1 2 3 4 5
字符串：A B A B A C
next : 0 0 1 2 3 0

乍一看可能看不出来什么规律，我们一个一个来看一下，我们先看第一个非零数字1，它在第2个位置。它指的是，在前3个字母组成的字符串中，前1个字母和后1个字母相同。

在来看处在第4个位置上的数字2，它的意思就表示前4个字母组成的字符串中前2个字母与后2个字母相同。

那么第5个位置的3即为前5个字母组成的字符串中前3个字母与后3个字母相同。

0的位置都表示前 i 个位置上首尾都不相同。

KMP算法匹配模式

知道了next数组，我们就可以来学习KMP算法的匹配模式。

1730021016405

当P串与S串匹配到第4个字符时，出现了失配，若是按照BF算法，此时我们应该从 i= 1，j = 0 的地方从新开始匹配，但是这样的化，我们以及完成匹配的字符的就需要重新匹配一遍，我们仔细查看两个字符串，虽然第4个位置失配，但是第1个位置与第3个位置的字符相同，即next[2] = 1，我们可以直接保持i不变，令 j = 1，继续开始匹配。

就变成下面这样：

1730021335296

此时第7个位置又发生失配，但是next[5] = 3 ，则我们可以保持i不变，令：j = 3，继续匹配。

1730021457329

我们总结一下算法：

匹配过程中，i ++,j++。
若是遇到失配，则令j = next[j]，然后继续匹配。

代码如下：

bool IntIndex_KMP (char* s,char* p,int* pos,int* next) 
{  
  int i= 0; int j = 0;
  while(i<strlen(s) && j<strlen(p)) 
  {   
    if(s[i]==p[j])
    {
        i++,j++;  
    }
    else{
      while(j>0 && s[i]!=p[j])  //不匹配时，j回退
      {
        j=next[j-1];  //i不变 j回退
      }
      if(s[i]!=p[j])  //j回退到0还不匹配
      {
        i++;
      }
    }
  }
  if (j == strlen(p))
  {
    *pos = i - strlen(p);
    return true;/*匹配成功*/
  }
  else{
    pos = NULL;   
    return false;/*返回不匹配标志*/
  }
}

next数组实现

现在我们只需要学会如何计算next数组。

在计算next数组时，我们运用两种思想，一种是递推，一种是KMP匹配算法，没错，在计算next数组时，我们仍然用到了KMP匹配的思想。

首先在只有一个字母时，我们规定next[0] = 0。

接下来，我们根据这一点开始递推，递推规则如下：（设置两个变量，j = 0,i = 1)）

p[i] == p[j] ,next[i] = ++j
p[i] != p[j], 令 j = next[j-1]
if j == 0, next[i] = 0

我们发现其实第2条与KMP匹配的代码非常相似

1730027272471

对于这个P，当d 与c失配时，我们从next[now-1]得知，尾部的ab与开头的两个字母相等，所以令now = next[now-1] 则我们可以直接跳跃到下一个能够匹配c前面ab的地方，再检查第3个字符是否相等即可。

计算next数组代码如下：

int* get_next(char* p,int* mn)
{
    size_t m = -1;
    for(m = 0;p[m]!= '\0';m++);
    *mn = m;
    int* next = (int*)malloc(sizeof(int)*m);
    next[0] = 0;
    int i = 1,j = 0;
    while(i<m)
    {
        if(p[i] == p[j])
        {
            j++;
            next[i++] = j;
        }
        else
        {
            if (j == 0)
                next[i++] = 0;
            else
                j = next[j-1];
        }
    }
    return next;
}

在0下边存放串的长度

在0下标存放数组的长度，我们让p与next 的下标对其，next[0] = 0,next[1] = 0。那么我们原来的next数组需要全体右移一位，并且每一位+1。然后我们舍去最后一位的值，并集给第一个值的next值标记为0：

1735040431091

则此时next计算代码改为如下：

int* get_next(char* p)
{
    int* next = (int*)malloc(sizeof(int)*p[0]);
    next[0] = 0,next[1] = 0;
    int i = 1,j = 0;
    while(i<p[0])
    {
        if(j == 0 ||p[i] == p[j])
        {
            i++,j++;
            next[i] = j;
        }
        else
        {
          j = next[j];
        }
    }
    return next;
}

计算nextval 的代码如下：

int* get_nextval(char* p)
{
    int* next = (int*)malloc(sizeof(int)*p[0]);
    next[0] = 0,next[1] = 0;
    int i = 1,j = 0;
    while(i<p[0])
    {
        if(j == 0 ||p[i] == p[j])
        {
            i++,j++;
            if(p[i] != p[j])
                next[i] = j;
            else
                next[i] = next[j];
        }
        else
        {
          j = next[j];
        }
    }
    return next;
}

示例：

计算nextcal的思想主要是：

在next数组中挨个遍历，如果a[i] == a[next[i]]，则让nextval中nextval[i] = nextval[next[i]]

1735040892373

此时kmp算法代码如下：

bool IntIndex_KMP (char* s,char* p,int* pos,int* nextval) 
{  
  int i= 1; int j =1;
  while(i<=s[0] && j<=p[0])
  {   
    if(j==0 || s[i]==p[j])
      i++;j++;  
    else 
      j=nextval[j];  //i不变 j回退
  }
  if (j>p[0])
  {  
    *pos = i-p[0];/*匹配成功，返回子串T在主串S中的位置*/
    return true;/*匹配成功*/
  }
  else   
    return false;/*返回不匹配标志*/
}

数据结构_串_

串