一、串顺序存储

1、定义

• 静态数组实现

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

• 动态数组实现

typedef struct {
    char* ch; //按串长分配存储区间
    int length;
}HString;

2、初始化（下面都用静态数组实现）

void InitString(SString& S) {
    S.length = 0;
}

3、赋值操作

bool StrAssign(SString& T, char* chars) {
    while (true)
    {
        if (chars[T.length]) {
            T.ch[T.length] = chars[T.length];
            T.length++;
        }
        else
        {
            break;
        }
    }
    return true;
}

4、复制操作

bool StrCopy(SString& T, SString S) {
    for (int i = 0; i < S.length; i++) {
        T.ch[i] = S.ch[i];
    }
    T.length = S.length;
    return true;
}

5、判空

bool StrEmpty(SString S) {
    if (S.length == 0)
        return true;
    else
        return false;
}

6、求串长

int StrLength(SString S) {
    return S.length;
}

7、清空操作

bool ClearString(SString& S) {
    for (int i = 0; i < S.length; i++) {
        S.ch[i] = NULL;
    }
    S.length = 0;
    return true;
}

8、串连接

bool Concat(SString& T, SString S1, SString S2) {
    for (int i = 0; i < S1.length; i++) {
        T.ch[i] = S1.ch[i];
    }
    for (int i = S1.length; i < S1.length + S2.length; i++) {
        T.ch[i] = S2.ch[i - S1.length];
    }
    T.length = S1.length + S2.length;
    return true;
}

9、求子串

bool SubString(SString& Sub, SString S, int pos, int len) {
    if (pos + len - 1 > S.length) {
        return false;
    }
    for (int i = pos - 1; i < pos + len-1; i++)
        Sub.ch[i - pos + 1] = S.ch[i];
    Sub.length = len;
    return true;
}

10、比较

int StrCompare(SString S, SString T) {
    for (int i = 0; i < S.length && i < T.length; i++) {
        if (S.ch[i] != T.ch[i])
            return S.ch[i] - T.ch[i];
    }
    return S.length - T.length;
}

11、定位

int Index(SString S, SString T) {
    int i = 0, n = StrLength(S), m = StrLength(T);
    SString sub;//暂存子串
    InitString(sub);
    while (i<n-m)
    {
        SubString(sub, S, i, m);
        if (StrCompare(T, sub) != 0)
            i++;
        else
            return i;
    }
    return -1;
}

二、链式存储

1、定义

typedef struct StringNode {
    char ch;
    struct StringNode* next;
}StringNode, *String;

2、提高存储密度的定义

typedef struct StringNode {
    char ch[4];
    struct StringNode* next;
}StringNode, *String;

三、匹配算法

1、朴素模式匹配

int Index(SString S, SString T) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            i++;
            j++;
        }
        else {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > T.length)
        return i - T.length;
    else
        return 0;
}

2、KMP

1）求next

void next(SString T, int* nexts) {
    
    nexts[1] = 0;
    nexts[2] = 1;
    for (int i = 3; i <= T.length; i++) {
        int j = i - 3;
        int count = 0;
        int temp_i = i-1;
        while (j>0)
        {
            if (T.ch[temp_i] == T.ch[j]) {
                count++;
                temp_i--;
                j--;
            }
            else
            {
                count = 0;
                j--;
                temp_i = i-1;
            }
        }
        if (count == 0)
            nexts[i] = 1;
        else
            nexts[i] = count+1;
    }
}

2)优化KMP（优化next）求nextval

void nextval(SString T, int* nexts, int* nextvals) {
    nextvals[1] = 0;
    for (int i = 2; i <= T.length; i++) {
        if (T.ch[i] == T.ch[nexts[i]])
            nextvals[i] = nextvals[nexts[i]];
        else
            nextvals[i] = nexts[i];
    }
}

3)KMP算法实现

int Index_KMP(SString S, SString T, int next[]) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            i++;
            j++;
        }
        else
            j = next[j];
    }
    if (j > T.length)
        return i - T.length;
    else
        return 0;
    
}