Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/9.串.md

9.1 串的定义与基本实现

#include "cstdio"

#define MaxLength 256

typedef struct {
    char ch[MaxLength];
    int length;
} SeqString;

bool InitSeqString(SeqString &S) {
    S.ch[1] = '\0';
    S.length = 0;
    return true;
}


/*
函数模板 -- 获取形参数组的长度
template<class T>
int length(T &array) {
    return sizeof(array) / sizeof(array[0]);
}
 */

template<class T>
bool StrAssign(SeqString &S, T &chars) {
    int len = sizeof(chars) / sizeof(chars[0]) - 1;
    if (len + 1 > MaxLength) {
        return false;
    }
    for (int i = 1; i <= len; ++i) {
        S.ch[i] = chars[i - 1];
    }
    S.length = len;
    return true;
}

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

int StrCompare(SeqString S, SeqString T) {
    for (int i = 1; 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;
}

int Index(SeqString S, SeqString SubT) {
    SeqString substring;
    InitSeqString(substring);
    int n = S.length;
    int m = SubT.length;
    int i = 1;
    while (i <= n - m + 1) {
        SubString(substring, S, i, m);
        if (StrCompare(substring, SubT) != 0) {
            i++;
        } else {
            return i;
        }
    }
    return 0;
}

int GetIndex(SeqString S, SeqString T) {
    int i = 1;
    int 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;
    }
}

template<class Type>
void GetNextArray(SeqString T, Type &next) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

template<class Type>
void GetNextValArray(SeqString T, Type &nextVal) {
    int i = 1, j = 0;
    nextVal[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            i++;
            j++;
            if (T.ch[i] != T.ch[j]) {
                nextVal[i] = j;
            } else {
                nextVal[i] = nextVal[j];
            }
        } else {
            j = nextVal[j];
        }
    }
}

void printArray(char chars[], int array[], int length) {
    printf("%s = [ ", chars);
    for (int i = 1; i <= length; ++i) {
        printf("%d ", array[i]);
    }
    printf("]\n");
}

int main() {
    SeqString S;
    SeqString T;
    InitSeqString(S);
    InitSeqString(T);

    StrAssign(S, "ABDCDFGVDDDBCE");
    StrAssign(T, "ababaa");
    int index = Index(S, T);
    int index2 = GetIndex(S, T);
    printf("index = %d\n", index);
    printf("index2 = %d\n", index2);
    int next[256];
    int nextVal[256];
    GetNextArray(T, next);
    GetNextValArray(T, nextVal);
    char nextStr[] = "next";
    char nextValStr[] = "nextVal";
    printArray(nextStr, next, T.length);
    printArray(nextValStr, nextVal, T.length);
    return 0;
}

9.2 串的模式匹配 -- KMP

template<class Type>
void GetNextArray(SeqString T, Type &next) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

template<class Type>
void GetNextValArray(SeqString T, Type &nextVal) {
    int i = 1, j = 0;
    nextVal[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            i++;
            j++;
            if (T.ch[i] != T.ch[j]) {
                nextVal[i] = j;
            } else {
                nextVal[i] = nextVal[j];
            }
        } else {
            j = nextVal[j];
        }
    }
}

//=====切割线======
nextVal[1] = 0;
for (int j = 2; j <= T.length; j++) {
    if (T.ch[next[j]] == T.ch[j]) {
        nextVal[j] = nextVal[next[j]];
    } else {
        nextVal[j] = next[j];
    }
}