数据结构入门-字符串

字符串

**串：**又称字符串，是由零个或多个字符组成的有限序列。

**串长：**串中字符的个数，例如 S 的串长为 6。

**空串：**零个字符的串，串长为 0。

**子串：**串中任意个连续的字符组成的子序列，称为该串的子串，原串称为子串的主串。

注意：空格也算一个字符。

**空格串：**全部由空格组成的串为空格串。

注意：空格串不是空串。

顺序存储：

1. 以’\0’表示字符串结束：

   在 C、C++、Java 语言中，通常用’\0’表示字符串结束，'\0’不算在字符串长度内。

2. 在 0 空间存储字符串的长度：

   下标为 0 的空间不使用，因此可以预先分配 Maxsize+1 的空间，在下标为 0 的空间中存储字符串长度。

3. 结构体变量存储字符串的长度：

   串的运算如合并、插入、替换等操作，容易超过最大长度，出现溢出。为了解决这个问题，可以采用动态分配空间的方法，其结构体定义如下。

   typedef struct {
   	char *ch;  //指向字符串指针
   	int length;  //字符串的长度
   }SString

链式存储：

单链表存储字符串时，虽然插入和删除非常容易，但是这样做也有一个问题：一个节点只存储一个字符，如果需要存储的字符特别多，会浪费很多空间。

因此也可以考虑一个节点存储多个字符的形式，例如一个节点存储 3 个字符，最后一个节点不够 3 个时用#代替。

但是这样做也有一个大问题：如在第 2 个字符之前插入一个元素，就需要将 b 和 c 后移，那么这种后移还要跨到第二个节点，如同“蝴蝶效应”，一直波及最后一个节点，麻烦就大了！

因此字符串很少使用链式存储结构，还是使用顺序存储结构更灵活一些。

模式匹配BF算法

**模式匹配：**子串的定位运算称为串的模式匹配或串匹配。

假设有两个串 S、T，设 S 为主串，也称正文串；T 为子串，也称模式。

在主串 S 中查找与模式 T 相匹配的子串，如果查找成功，返回匹配的子串第一个字符在主串中的位置。

最笨的办法就是穷举所有 S 的所有子串，判断是否与 T 匹配，该算法称为 **BF（Brute Force）**算法。

步骤：

1. 从 S 第 1 个字符开始，与 T 第 1 个字符比较，如果相等，继续比较下一个字符，否则转向下一步；
2. 从 S 第 2 个字符开始，与 T 第 1 个字符比较，如果相等，继续比较下一个字符，否则转向下一步，以此类推；
3. 如果 T 比较完毕，则返回 T 在 S 中第一个字符出现的位置；
4. 如果 S 比较完毕，则返回 0，说明 T 在 S 中未出现。

#include<iostream>
#include<cstring>
using namespace std;

#define Maxsize 100

typedef char SString[Maxsize+1];//0号单元存放串的长度

bool StrAssign(SString &T,char *chars)//生成一个其值等于chars的串T
{
	int i;
	if(strlen(chars)>Maxsize)
		return false;
	else
    {
		T[0]=strlen(chars);
		for(i=1;i<=T[0];i++)
        {
            T[i]=*(chars+i-1);
            cout<<T[i]<<"  ";
        }
        cout<<endl;
		return true;
	}
}

int Index_BF(SString S,SString T,int pos)//BF算法
{ 	// 求T在主串S中第pos个字符之后第一次出现的位置
	//其中，T非空，1≤pos≤s[0],s[0]存放S串的长度
	int i=pos,j=1,sum=0;
	while(i<=S[0]&&j<=T[0])
    {
        sum++;
        if(S[i]==T[j]) // 如果相等，则继续比较后面的字符
		{
			i++;
			j++;
		}
		else
		{
			i=i-j+2; //i退回到上一轮开始比较的下一个字符
			j=1;  //j退回到第1个字符
		}
    }
	cout<<"一共比较了"<<sum<<"次"<<endl;
	if(j>T[0]) // 匹配成功
		return i-T[0];
	else
		return 0;
}

算法复杂度分析：

设 S、T 串的长度分别为 n、m，则 BF 算法的时间复杂度分为以下两种情况：

1. 最好情况

   在最好情况下，每一次匹配都在第一次比较时发现不等。

   假设第 i 次匹配成功，则前 i−1 次匹配都进行了 1 次比较，一共 i−1 次，第 i 次匹配成功时进行了 m 次比较，则总的比较次数为 i−1+m

   即模式串正好在主串的最后端。

   假 设 每 一 次 匹 配 成 功 的 概 率 均 等 ， 概 率p i =1/(n−m+1)，则在最好情况下，匹配成功的平均比较次数为：

   

   最好情况下的平均时间复杂度为 O(n+m)。

2. 最差情况

   在最坏情况下，每一次匹配都比较到 T 的最后一个字符发现不等，回退重新开始，这样每次匹配都需要比较 m 次

   假设第 i 次匹配成功，则前 i−1 次匹配都进行了 m 次比较，第 i 次匹配成功时也进行 m次比较，则总的比较次数为 i×m

   在匹配成功的情况下，最多需要 n−m+1 次匹配，即模式串正好在主串的最后端

   假设每一次匹配成功的概率均等，概率 p i=1/(n−m+1)，则在最坏情况下，匹配成功的平均比较次数为：

   

   最坏情况下的平均时间复杂度为 O(n×m)。

模式匹配KMP算法

步骤：

按照 BF 算法，如果匹配的字符串不等，则 i 回退到 i−j+2，j 回退到 1，即 i=2，j=1：

其实 i 不用回退，让 j 回退到第 3 个位置，接着比较即可：

那怎么知道 T 中开头的两个字符和 i 指向的字符前面的两个字符一模一样？难道还要比较？

我们发现 i 指向的字符前面的两个字符和 T 中 j 指向的字符前面两个字符一模一样，因为它们一直相等， i++、j++才会走到当前的位置：

也就是说，我们不必判断开头的两个字母和 i 指向的字符前面的两个字符是否一样，只需要在 T 本身比较就可以了。

假设 T 中当前 j 指向的字符前面的所有字符为 T′，只需要比较T′的前缀和 T′的后缀即可：

注意：前缀和后缀不可以取字符串本身。如果串的长度为 n，前缀和后缀长度最多达到 n−1

因此，当 i、j 指向的字符不等时，只需要求出 T′的相等前缀后缀的最大长度 l，i 不变，j 回退到 l+1的位置继续比较即可。

**这样找所有的前缀和后缀比较，是不是也是暴力穷举？那怎么办呢？**可以用动态规划递推

有了 next[]数组，就很容易进行模式匹配了，当 S[i]≠T[j]时，i 不动，j 回退到 next[j]的位置继续比较即可。

void get_next(SString T,int next[])//计算next函数值
{
	int j=1,k=0;
	next[1]=0;
	while(j<T[0])
	{

	    if(k==0||T[j]==T[k])
            next[++j]=++k;
		else
			k=next[k];
	}
    cout<<"-----next[]-------"<<endl;
    for(j=1;j<=T[0];j++)
        cout<<next[j]<<"  ";
    cout<<endl;
}

int Index_KMP(SString S,SString T,int pos,int next[])//KMP算法
{ 	// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
	//其中，T非空，1≤pos≤StrLength(S)
	int i=pos,j=1,sum=0;
	while(i<=S[0]&&j<=T[0])
    {
        sum++;
        if(j==0||S[i]==T[j]) // 继续比较后面的字符
		{
			i++;
			j++;
		}
		else
			j=next[j]; // 模式串向右移动
    }
	cout<<"一共比较了"<<sum<<"次"<<endl;
	if(j>T[0]) // 匹配成功
		return i-T[0];
	else
		return 0;
}

算法复杂度分析：

设 S、T 串的长度分别为 n、m。KMP 算法的特点是：i 不回退，当 S[i]≠T[j]时，j 回退到 next[j]，重新开始比较。

最坏情况下扫描整个 S 串，其时间复杂度为 O(n)。

计算 next[]数组需要扫描整个 T 串，其时间复杂度为 O(m)，因此总的时间复杂度为 O(n+m)。

需要注意的是，尽管 BF 算法最坏情况下时间复杂度为 O(n×m)，KMP 算法的时间复杂度为 O(n+m)。但是在实际运用中，BF 算法的时间复杂度一般为 O(n+m)，因此仍然有很多地方用 BF 算法进行模式匹配。

只有在主串和子串有很多部分匹配的情况下，KMP 才显得更优越。

改进的KMP算法

步骤：

在 KMP 算法中，next[]求解非常方便、迅速，但是也有一个问题：当 s i≠t j 时，j 回退到 next[j]（k=next[j]），然后 s i 与 t k 比较。这样的确没错，但是如果 t k=t j，这次比较就没必要了，因为刚才就是因为 s i≠t j 才回退的，那么肯定 s i≠t k，完全没必要再比了：

再向前回退，找下一个位置 next[k]，继续比较就可以了。当 si≠tj 时，本来应该 j 回退到next[j]（k=next[j]），si 与 t k 比较。

但是如果 t k=t j，则不需要比较，继续回退到下一个位置 next[k]，减少了一次无效比较。

void get_next2(SString T,int next[])//计算next函数值改进算法
{
	int j=1,k=0;
	next[1]=0;
	while(j<T[0])
	{

	    if(k==0||T[j]==T[k])
        {
            j++;
            k++;
            if(T[j]==T[k])
                next[j]=next[k];
            else
                next[j]=k;
        }
		else
			k=next[k];
	}
    cout<<"-----next[]-------"<<endl;
    for(j=1;j<=T[0];j++)
        cout<<next[j]<<"  ";
    cout<<endl;
}

算法复杂度分析：

设 S、T 的长度分别为 n、m。改进的 KMP 算法只是在求解 next[]从常数上的改进，并没有降阶，因此其时间复杂度仍为 O(n+m)。

字符串的应用–病毒检测

**题目：**疫情暴发，专家发现了一种新型环状病毒，这种病毒的 DNA 序列是环状的，而人类的 DNA 序列是线性的。专家把人类和病毒的 DNA 表示为字母组成的字符串序列，如果在某个患者的 DNA 中发现这种环状病毒，说明该患者已被感染病毒，否则没有感染。

思路：

该问题属于字符串的模式匹配问题，可以使用前面讲的 BF 或 KMP 算法求解。这里需要对环状病毒进行处理，然后调用模式匹配算法即可。

处理环状病毒：

1. 环形处理

   使用循环存储的方式，类似循环队列或循环链表的处理方式。假设病毒的 DNA 长度为m，依次从环状存储空间中每一个下标开始，取 m 个字符作为病毒序列：

   

2. 线性处理

   将病毒序列扩大两倍，依次从每个下标开始，取 m 个字符，作为病毒序列。

   例如，病毒序列：aabb，如图 4-45 所示。将该病毒序列扩大两倍。从每个下标（1、2、3、4）开始取 4 个字符，分别为 aabb、abba、bbaa、baab，这 4 个序列都是病毒序列的变种：

   

步骤：

1. 首先对环状病毒进行处理（环形处理或线性处理）。
2. 依次把每一个环状病毒变种作为子串，把患者 DNA 序列作为主串，进行模式匹配。一旦匹配成功，立即结束，返回已感染病毒。
3. 重复运行第 2 步。
4. 如果检测所有病毒变种都未匹配成功，返回未感染病毒。

bool Virus_detection(SString S, SString T)//病毒检测
{
    int i,j;
    SString temp;//temp记录病毒变种
    for(i=T[0]+1,j=1;j<=T[0];i++,j++)//将T串扩大一倍，T[0]为病毒长度
        T[i]=T[j];
    for(i=0;i<T[0];i++)//依次检测T[0]个病毒变种
    {
        temp[0]=T[0];////病毒变种长度为T[0]
        for(j=1;j<=T[0];j++)//取出一个病毒变种
            temp[j]=T[i+j];
        if(Index_KMP(S,temp,1))//检测到病毒
            return 1;
    }
    return 0;
}

算法复杂度分析：

假设病毒 DNA 序列长度为 m，则一共有 m 个变种，需要进行 m 次模式匹配，每次模式匹配如果使用 KMP 算法，其时间复杂度为 O(n+m)，则总的时间复杂度为 O(m×(n+m))。