串

串的定义与实现

字符串简称串，由零个或多个字符组成的有限序列

定长顺序存储

采用一组连续的存储单元来存储串值的字符序列

typedef struct
{
    char ch[MAXSIZE];
    int length;
} SString;

堆分配存储

typedef struct
{
    char *ch;
    int length;
} HString;

块链存储表示

采用链表的方式存储串值，在具体实现时，每个结点可以存放一个或多个字符，每个结点被称为块，整个链表成为块链结构

串的模式匹配

简单的模式匹配算法

字串的定位操作被称为串的模式匹配，求字串在主串的位置。

int index(HString *S, HString *T)
{
    int i = 0, j = 0;
    while (i < S->length && j < T->length)
    {
        if (S->ch[i] == T->ch[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= T->length)
    {
        return i - T->length;
    }
    else
    {
        return 0;
    }
}

串模式匹配算法——KMP算法

void computeNextArray(HString *T, int *next)
{
    next[0]=0;
    if(T->length == 1){
        return;
    }
    int j = 0;
    next[1] = 0;
    for (int i = 2; i < T->length; i++)
    {
        while (j > 0 && T->ch[i] != T->ch[j])
        {
            j = next[j - 1];
        }
        if (T->ch[i] == T->ch[j])
        {
            j++;
        }
        next[i] = j;
    }
}

int indexKMP(HString *S, HString *T)
{
    if (T->length == 0)
    {
        return 0;
    }

    int *next = (int *)malloc(T->length * sizeof(int));
    if (next == NULL)
    {
        cout << "内存分配失败" << endl;
        return -1;
    }

    computeNextArray(T, next);

    int j = 0;
    for (int i = 0; i < S->length; i++)
    {
        while (j > 0 && S->ch[i] != T->ch[j])
        {
            j = next[j - 1];
        }
        if (S->ch[i] == T->ch[j])
        {
            j++;
        }
        if (j == T->length)
        {
            free(next);
            return i - T->length + 1;
        }
    }
    free(next);
    return -1;
}