6.串

第一章 自测&关键词回顾

一个人能走的多远, 不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。——KMP
KMP: _阿岳_

第二章 手撕

①就是定长顺序表, 存char; 和顺序表的实现99%相同; ②相关操作, 不如去把string.h看看

第三章 相关应用

第一节 BF算法

aimS的每个区间, 都要和moduleS全部判断

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

#define N 1000

void BF(char *aimS, char *moduleS) {
    for (int index = 0; index < strlen(aimS); index++) {
        for (int i = index, j = 0; j < strlen(moduleS); i++, j++) {
            if (aimS[i] != moduleS[j]) break;
            if (j == strlen(moduleS) - 1) { // 成功匹配
                int begin = index;
                int end = i ;
                printf("%d %d\n", begin, end);
                break;
            }
        }
    }
}

int main() {
    char aimS[N], moduleS[N];
    scanf("%s", aimS);
    scanf("%s", moduleS);
    BF(aimS, moduleS);
    return 0;
}

第二节 KMP算法

KMP: _阿岳_

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

#define N 100

void getNext(int *next, char *moduleS) {
    next[0] = -1;
    for (int i = 1; i < strlen(moduleS); i++) {
        int t = next[i - 1];
        while (t != -1 && moduleS[t] != moduleS[i - 1]) { t = next[t]; }
        next[i] = t + 1;
    }
}

void KMP(int *next, char *aimS, char *moduleS) {
    for (int i = 0, j = 0; i < strlen(aimS); i++) {
        while (j != 0 && aimS[i] != moduleS[j]) j = next[j];
        if (aimS[i] == moduleS[j]) j++;
        if (j == strlen(moduleS)) {
            int begin = i - strlen(moduleS) + 1;
            int end = i;
            printf("%d %d\n", begin, end);
            j = next[j - 1] + 1;
        }
    }
}

int main() {
    char aimS[N], moduleS[N];
    int next[N];
    scanf("%s", aimS);
    scanf("%s", moduleS);
    // Next数组
    getNext(next, moduleS);
    for (int i = 0; i < strlen(moduleS); i++) printf("%d ", next[i]);
    puts("");
    // KMP
    KMP(next, aimS, moduleS);
    return 0;
}

第四章 上手真题

第五章 比赛怎么用