串（string）(或字符串)

• 由零个或多个字符组成的有限序列
• 空串：长度为零的串
• 子串：串中任意个连续的字符组成的子序列
• 空格串：由一个或多个空格组成的串
• ‘\0’：结束标记

串的表示与实现

定长顺序存储表示

• 用一组地址连续的存储单元存储串值的字符序列。
• 为每个定义的串变量分配一个固定长度的存储区
• 超过预定义长度的串值被省去，称之为“截断”

typedef struct
{
    char str[maxSize+1];
    //多出一个'\0'作为结束标记
    int length;
}Str;

变长分配存储（动态分配存储）

• 在使用时，需要用函数malloc()来分配一个长度为length、类型为char型的连续存储空间
• 分配的空间可以用free()释放

typedef struct
{
    char *ch; //指向动态分配存储区首地址的字符指针
    int length;
}Str;

堆分配存储表示

- 以一组地址连续的存储单元存放串值字符序列
- 存储空间是在程序执行过程中动态分配而得

块链存储表示

- 采用链表方式存储串值

串的模式匹配算法

• 模式匹配：子串的定位操作
• Index(S, T, pos)
• 子串T称为模式串
• 从主串S的第pos个字符起和模式的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，函数值为和模式T中的第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为零
• 此字符串存储在1-length位置上

int index(Str str, Str subStr)//str:主串 subStr:子串
{
    int i=1,j=1,k=i;
    while(i<=str.length && j<=subStr.length)
    {
        if(str.ch[i] == subStr.ch[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j=1;
            i=++k;
        }
    }
    if(j>subStr.length)
        return k;
    else return 0;
}

克努特-莫里斯-普拉特操作（简称为KMP法）

• 每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右滑动尽可能多的一段距离后，继续进行比较
• next数组：模式串j处不匹配时，应从next[j]处的字符开始重新与主串进行比较

void getNext(Str subStr, int next[])
{
    int i=1,j=0;
    next[1]=0;
    while(i<subStr.length)
    {
        if(j==0||subStr.ch[i]==subStr.ch[j])
        {
            ++i;
            ++j;
            next[i]=j;
        }
        else
            j=next[j];
    }
}

int KMP(Str str,Str subStr,int next[])
{
    int i=1,j=1;
    while(i<=str.length && j<=substr.length)
    {
        if(j==0||str.ch[i]==subStr.ch[j])
        {
            ++i;
            ++j;
        }
        else
            j=next[j];
    }
    if(j>subStr.length)
        return i-subStr.length;
    else
        return 0;
}

https://blog.csdn.net/v_july_v/article/details/7041827