串类型

存储结构

串的存储结构可以使用顺序和链式结构，顺序结构中又分为定长和堆式存储结构，但由于链式不如顺序结构灵活，操作简单，故而此处只写入顺序结构

顺序-定长存储

typedef struct{
	char ch[maxsize+1];		//定义字符数组，串的最大长度为maxsize，多申请防止溢出的存储空间
	int length;				//串的当前长度
}Sstring;

顺序-堆式存储

typedef struct{
	char *ch;				//如果是非空串，则按串长分配存储区，否则ch指向NULL;
	int length;				//串的当前长度
}

模式匹配算法

串的模式匹配用于在主串中寻找子串，如果匹配成功，则确定相匹配的子串中第一个字符在主串s中出现的位置

BF算法

int Index_BF(Sstring s,Sstring t,int pos)
    //传址需要比较的主串s，子串t，以及从主串序号为pos处开始查找
{
    int i,j;
    for(i=pos,j=1;i<=s.length&&j<=t.length;i++,j++)
        //初始化i=pos,j=1，当两个串都没有到串尾时循环，i，j依次后移
    {
        if(s.ch[i]==t.ch[i])	//当主串s中i位置的字符和子串t中j位置的字符相同时
        {
            continue;		//继续下一次循环，即只执行for语句的i++，j++
        }
        else
        {
            i=i-j+1;		//否则，i回到开始匹配的位置（执行for语句的i++后移到下一个位置
            j=0;			//j被重置为0（然后执行for语句的j++后变为j=1）
        }
    }
    if(j>t.length) return i-t.length;
    //当j的位置超出了t的长度，则说明完全匹配，返回首字符开始与主串匹配的位置
    else return 0;
    //否则返回0，表示没有匹配成功
}

KMP算法

int Index_KMP(Sstring s,Sstring t,int pos)
    //传址需要比较的主串s，子串t，以及从主串序号为pos处开始查找
{
    int i,j;
    for(i=pos,j=1;i<=s.length&&j<=t.length;i++,j++)
        //初始化i=pos,j=1，当两个串都没有到串尾时循环，i，j依次后移
    {
        if(j==0||s.ch[i]==t.ch[i])	//当主串s中i位置的字符和子串t中j位置的字符相同时
        {
            continue;		//继续下一次循环，即只执行for语句的i++，j++
        }
        else
        {
            j=next[j];		//KMP相比BF算法节省时间的原因
        }
    }
    if(j>t.length) return i-t.length;
    //当j的位置超出了t的长度，则说明完全匹配，返回首字符开始与主串匹配的位置
    else return 0;
    //否则返回0，表示没有匹配成功
}

void get_next(Sstring t,int next[])
    //求子串t的next函数值并且存进数组next
{
    int j,i=1,next[1]=0;
    //定义i，j，以及next数组的第一个值
    for(j=0;i<t.length;)				//i不超过子串t长度时循环
    {
        if(j==0||t.ch[i]==t.ch[j])		//如果j为0或是前后两个字符相同时
        {
            i++;
            j++;
            if(t.ch[i]!=t.ch[j])		//如果前后两个字符不相同
                next[i]=j;				//令下次比较从j开始
            else next[i]=next[j];		
        }
        else j=next[j];
    }
}