本文共 3578 字，大约阅读时间需要 11 分钟。

1.串的定义

 串是仅有字符构成的有限序列，是一种线性表。一般记为S='a1a2...an',其中，S是串名，单引号括起来的字符序列是是串值。

2.串的几个基本概念

1）空串：长度为零的串。

2）空格串：由一个或多个空格组成的串，空格也是一个字符。

3）子串：由串中任意长度的连续字符构成的序列，含有子串的串称为主串。子串在主串中的位置是指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。

3.串的基本操作

1） 初始化

#define MAX_SIZE 100typedef struct{	char *ptr;  //串存放的起始地址	int length; //串的长度}String;int init(String *str){	str->length = 0;	str->ptr = (char *)malloc(MAX_SIZE * sizeof(char));	if (str->ptr)	{		return 0;	}	else	{		return -1;	}}

2） 判断空

bool isEmpty(String* str){	if (str->length == 0)	{		return true;	}	else	{		return false;	}}

3）赋值

void strAssign(String *str, char ch[]){	int i = 0;	//计算第二个字符串的长度	while (ch[i] != '\0')	{		i++;	}	str->length = i;	if (i > MAX_SIZE)	{		str->ptr = (char *)realloc(str->ptr, i+1);	}	for (i = 0; i < str->length; i++)	{		//从第一个字符开始，着个赋值		str->ptr[i] = ch[i];	}	str->ptr[str->length] = '\0';}

4）连接 

void Concat(String* s1, char ch[]){	int i = 0;	//计算第二个字符串的长度	while (ch[i] != '\0')	{		i++;	}	//判断总共有多少字符,如果大于最大则重新申请空间,再赋值	int totalSize = s1->length + i;	if (totalSize <= MAX_SIZE)	{		for (int j = 0; j < i; j++)		{			s1->ptr[s1->length + j] = ch[j];		}		s1->ptr[totalSize] = '\0';	}	else	{		s1->ptr = (char *)realloc(s1->ptr, totalSize + 1);		for (int j = 0; j < i; j++)		{			s1->ptr[s1->length + j] = ch[j];		}		s1->ptr[totalSize] = '\0';	}}

4）串的模式匹配

（1）布鲁特-福斯算法（BF）

从主串的第一个字符起与模式串的第一个字符比较，如果相等，则继续逐一对字符串的字符进行后续比较；如果不相等，则从主串第二个字符起与模式串的第一个字符重新比较，直到模式串中每个字符依次和主串中一个连续的字符序列相等为止，此时匹配成功；否则，匹配失败。

//从pos开始的位置，查找模式串t在主串s串中是否存在int index(char s[],char t[],int pos){    //i,j分别用于指出主串字符和模式串字符的位置    int i,j;    int sLen,tLen;    i = pos;    j = 0;    sLen = strlen(s);    tLen = strlen(t);    while(i < sLen && j < tLen)    {        if(s[i] == t[j])        {            i++;            j++;        }        else        {            i = i-j+1;            j = 0;        }    }    if(j >= tLen)    {        return i-tLen;    }    return -1;}

（2）KMP算法

改进之处在于，每当匹配过程中出现相比较的字符不相等时，不需要回退主串的字符指针位置，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。在KMP算法中，依据模式串的next函数值实现子串的滑动。

解析：abababb,一个一个字符看，教大家一个方法，看除去最后一个字符的前两个字符。

默认next[0] = -1

ab:除去最后一个字符b,前面a，没有相同的前缀和后缀，则next[1] = 0;

aba:除去最后一个字符a,前面ab，没有相同的前缀和后缀，则next[2] = 0;

abab:除去最后一个字符b,前面aba,有相同的字符a ,next[3] = 0 + 1 =1;

ababa:除去最后一个字符a,前面abab，有相同的前缀和后缀ab,next[4] = 0+2 = 2;

ababab:除去最后一个字符b,前面ababa，有相同的前缀和后缀aba,next[5] = 0+3 = 3;

abababb:除去最后一个字符b,前面ababab，有相同的前缀和后缀abab,next[4] = 0+4 = 4;

以下为获取next函数的算法：

void get_next(char *p,int next[]){    int i,j,sLen;    sLen = strlen(p);    i = 0;    next[0] = -1;    j = -1;    while(i < sLen)    {        if(j == -1 || p[i] == p[j])        {            ++i;            ++j;            next[i] = j;        }        else        {            j = next[j];        }    }}

以下为KMP算法：

//利用模式串p的next函数，从第pos个字符开始，求p在主串s中是否存在int KMP(char *s,char *p,int pos,int next[]){    int i;    int j;    int sLen;    int pLen;    i = pos -1;    j = -1;    sLen = strlen(s);    pLen = strlen(p);    while(i < sLen && j < pLen)    {        if(j == -1 || s[i] == p[j])        {            ++i;            ++j;        }        else        {            j = next[j];        }    }    if(j >= pLen)    {        return i-pLen;    }    else    {        return -1;    }}

以下为KMP算法示意图： 

①第一次匹配从S[0]与P[0]开始，由于S[0]==P[0]，S[1]==P[1]，S[2]==P[2],比较S[3]和P[3],由于它们不相等，所以第一次匹配结束

②第二次匹配，令j = next[3] = 1，第二次从S[3]与P[1]开始比较，仍不相等，则第二次匹配结束

③第三次匹配，令j = next[1] = 0，第三次从S[3]与P[0]开始比较，仍不相等，则第三次匹配结束

④第四次匹配，令j = next[0] = -1，此时满足条件“j == -1”，显然不能令S[3]与P[-1]进行比较，说明主串中从i = 3开始的字串不可能与模式串相等，因此需要将 i 的值递增后再继续进行匹配，令i++,j++;

⑤第五次匹配，S[4]与P[0]比较，直到匹配完成