数据结构-串

串（String）

逻辑结构：受限线性表

存储结构：

定长顺序存储表示

#define Max 255
typedef struct{
    char ch[Max];
    int length;
}SString;

堆分配存储表示

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

链式存储表示

//size被自定义，表示一个结构体中存放多少个字符
#define size 4
typedef struct{
    char ch[size];
    LString *next;
}LString;

堆分配存储表示的详解

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

void initHString(HString *str, const char *source) {
    str->length = strlen(source);
    str->ch = (char *)malloc((str->length + 1) * sizeof(char)); // 分配内存
    if (str->ch == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
    strcpy(str->ch, source); // 复制字符串内容
}

void freeHString(HString *str) {
    free(str->ch); // 释放内存
    str->ch = NULL;
    str->length = 0;
}

int main() {
    HString myString;
    initHString(&myString, "Hello, World!");

    printf("String: %s\n", myString.ch);
    printf("Length: %d\n", myString.length);

    freeHString(&myString); // 释放内存

    return 0;
}

!(/img/2025_3_16/001.png)

串的简单模式匹配

int SMatch(char a[], char b[]) {
    char *ptra = a;
    char *temp = ptra;
    char *ptrb = b;
    while (*ptra != '\0') {
        temp = ptra;
        ptrb = b;
        while (*ptra == *ptrb && *ptrb != '\0') {
            ptra++;
            ptrb++;
        }
        if (*ptrb == '\0') {
            return 1;
        }
        ptra = temp + 1;
    }
    return 0;
}

int main(void) {
    char a[] = "ijijij";
    char b[] = "ijijij";
    printf("%d", Com(a, b));
}

简单模式匹配算法的时间复杂度为O(mn)

KMP算法

字符串的前缀、后缀与部分匹配值

404
此方法作为为手算Next数组的方法的理论来源

KMP算法旨在减少主串与辅串回溯的次数，降低算法的时间复杂度。核心是利用匹配失败后的信息。
假设主串S的长度为m，辅串T的长度为n，理论上最坏情况下迭代m-n+1轮，同时每轮进行n次比对，一共比较了(m-n+1)*n次，当m>>n时，时间复杂度为O(m*n)。KMP算法可将时间复杂度降低为O(m+n)。
如何求next数组

next[j] = -1：j = 0。表示如果辅串第一个字符不匹配，则主串指针递增，辅串指针不变。
next[j] = x:x = 最长相等前后缀长度。为什么要取最长？这样想，若next值尽量的大，则说明前面已经匹配的越多，那么辅串向后移动的位数也越少，如果不取最大值，引发辅串向后移动位数太多，可能会错过匹配的选项。主串指针改变，辅串指针改变。
next[j] = 0：其他情况。最坏情况下，从辅串第一个字符开始比较。主串指针不变，辅串指针该变。

代码：

// 匹配
int match (char* P, char* S){ // KMP 算法
    int* next = buildNext(P); // 构造 next 表
    int m = (int) strlen (S), i = 0; // 文本串指针
    int n = (int) strlen(P), j = 0; //模式串指针
    while (j < n && i < m) // 自左向右逐个比对字符
        if (0 > j || S[i] == P[j]) // 若匹配，或 P 已移除最左侧
            {i++; j++;} // 则转到下一字符
        else
            j = next[j]; // 模式串右移（注意：文本串不用回退）
    delete [] next; // 释放 next 表
    return i - j;
}

// 求Next数组
int* buildNext(char* P) { // 构造模式串 P 的 next 表
    size_t m = strlen(P), j = 0; // “主”串指针
    int* N = new int[m]; // next 表
    int  t = N[0] = -1; // 模式串指针
    while (j < m - 1)
        if ( 0 > t || P[j] == P[t]){ // 匹配
            j++; t++;
            N[j] = t; // 此句可改进为 N[j] = (P[j] != P[t] ? t : N[t]);
        }else // 失配
        t = N[t];
    return N;

}