串是由0或者多个字符组成的有限序列。一般记为S='aa1...an'
S是串名，ai可以是字母、数字或者其他字符；
串中字符个数n称为串的长度，n=0时的串称为空串
串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应的称为主串。某个字符在串中的序号称为该字符在串中的位置，当两个串的长度相等，且每个位置对应的字符相同，则这两个串是相等的
由一个或多个空格组成的串
用一组连续的存储单元存储串的字符序列，是一个固定长度的数组
问尤龙の时光
#include <stdio.h>
// 固定长度的串
typedef struct SString {
char ch[10];
int length;
}SString;
int main() {
SString str;
str.ch[0] = 'H';
str.ch[1] = 'e';
str.ch[2] = 'l';
str.ch[3] = 'l';
str.ch[4] = 'o';
str.ch[5] = '\0'; //字符串结尾需要添加'\0'作为终止符
// 输出验证
printf("%s\n", str.ch);
}
与定长顺序存储不同的是，堆内存存储使用一个指针指向数组，这个数组其实也是连续的，区别是使用malloc申请存储空间时，可以动态指定需要的空间长度，用完以后可以使用free释放这段空间
#include <stdio.h>
#include <stdlib.h>
// 固定长度的串
typedef struct HString {
char *ch;
int length;
}HString;
int main() {
HString str;
str.ch = (char*)malloc(sizeof(char)*10);
if (str.ch == NULL) {
printf("堆内存申请失败\n");
return -1;
}
str.ch[0] = 'H';
str.ch[1] = 'e';
str.ch[2] = 'l';
str.ch[3] = 'l';
str.ch[4] = 'o';
str.ch[5] = '\0'; //字符串结尾需要添加'\0'作为终止符
// 输出验证
printf("%s\n", str.ch);
}
字符串很长的时候，难以申请一块连续的内存空间，因此可以使用链表来存储字符，链表每个节点可以存储一个或者多个字符
#include <stdio.h>
#include <stdlib.h>
// 节点存储一个字符
typedef struct SingleCharLinkedString {
char ch;
struct SingleCharLinkedString* next;
}SingleCharLinkedString;
// 节点存储多个字符
typedef struct MultiCharLinkedString {
char ch1;
char ch2;
struct MultiCharLinkedString* next;
}MultiCharLinkedString;
// 节点存储定长字符数组
typedef struct FixedArrayLinkedString {
char ch[5];
struct FixedArrayLinkedString* next;
}FixedArrayLinkedString;
// 节点存储字符数组指针
typedef struct ArrayLinkedString {
char* ch;
struct ArrayLinkedString* next;
}ArrayLinkedString;
求解子串在主串中的位置称为串的模式匹配
暴力匹配步骤如下
初始化 ：设定两个指针，一个指向主字符串的起始位置（记作i），另一个指向子字符串的起始位置（记作j）。
比较 ：从i和j开始，逐个字符比较主字符串和子字符串的字符是否相等。
text[i] != pattern[j]），说明当前匹配失败，此时将主字符串的指针i回退到上次匹配开始的位置之后一位（即 i = i - j + 1），然后将子字符串的指针j重置为0，开始下一轮匹配。pattern[j]是 \0），则匹配成功，返回i的位置作为子字符串在主字符串中的起始索引。重复 ：如果主字符串未完全遍历完且未找到匹配，则重复步骤2，直到找到匹配或遍历完主字符串。
时间复杂度为O(m*n)，m为主串长度，n为子串长度，代码实现如下
#include<stdio.h>
#define MAIN_STR_LENGTH 13
#define SUB_STR_LENGTH 5
typedef struct SString {
char *str;
}SString;
int matchSubStr(char mainStr[], char subStr[]) {
for (int i = 0; i <= (MAIN_STR_LENGTH - SUB_STR_LENGTH); i++) {
int match = 1;
/*
* 从主串的第i个位置开始匹配子串,发现不匹配则将match标识为0，
* 同时跳出循环，从主串第i+个位置开始重新匹配
*/
for (int j = 0; j < SUB_STR_LENGTH; j++) {
if (mainStr[i + j] != subStr[j]) {
match = 0;
break;
}
}
if (match == 1) {
printf("从下标%d开始匹配子串", i);
return 1;
}
}
printf("找不到匹配串");
return 0;
}
int main() {
char mainStr[] = { 'a','b', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'c', 'b', 'a', 'b' };
char subStr1[] = { 'a', 'b', 'c', 'a', 'c' };
matchSubStr(mainStr, subStr1);
return 1;
}
暴力匹配每次遇到字符不匹配的情况，都需要将主串向后移动一位，然后从头开始匹配，再暴力匹配过程中，我们会发现，有些匹配其实是可以跳过的
如下图所示，在第三趟匹配中，i=6,j=4不匹配，但是前面的abca是匹配的，在暴力匹配中，我们需要在向后移动一位然后重新匹配，但实际上i=3、j=0和i=4、j=0以及i=5、j=0这三次匹配时没有必要进行的，直接将模式向右滑动三个字符的位置继续匹配i=6、j=1即可
某趟已经匹配相等的字符的序列，是模式的某个前缀，如果这个前缀序列中有某个后缀正好是模式的前缀，就可以将模式向后滑动到与这些相等字符对齐的位置
以abcac为例
| 子串 | 前缀 | 后缀 | 相同字符串 | 部分匹配值 |
|---|---|---|---|---|
| a | 空 | 空 | 空 | 0 |
| ab | a | b | 空 | 0 |
| abc | a、ab | c、bc | 空 | 0 |
| abca | a、ab、abc | a、ca、bca | a | 1 |
| abcac | a、ab、abc、abca | c、ac、cac、bcac | 空 | 0 |
所以abcac的部分匹配值为00010，构建一个部分匹配值(Partial Match,PM)的表如下
下面用这个表来做匹配(下标从0开始)
1、第一趟匹配
c与a不匹配，最后一个匹配字符b对应的部分匹配值是0，按照下面公式算出子串需要向后移动的位数：移动位数=已匹配字符数-对应的部分匹配值，因为2-0=2，所以将子串向后移动两位
2、第二趟匹配
发现c与b不匹配，最后一个匹配字符a对应的部分匹配值为1，4-1=3，将子串向后移动3位再次匹配
3、第三趟匹配
第三趟匹配已在主串中找到匹配子串
在真个匹配过程中，主串始终没有回退，所以KMP算法时间复杂度为O(m+n)
匹配过程中，如果对应的部分匹配值为0，即已匹配相等的序列中没有相等的前后缀，此时移动的位数最大，直接将子串首字符右移到主串i位置进行下一趟比较；如果已匹配相等序列中存在最大相等前后缀，将子串向右滑动到和该相等前后缀对齐，再从主串i位置进行下一趟比较
右移位数=已匹配字符数-对应的部分匹配值
记作Move = j-PM[j-1]
在上述操作中，我们的找的是失配字符的前一个字符的部分匹配值，如果我们将PM表右移一位，这样哪个字符匹配失败直接找自己的部分匹配值即可
这时下标从0开始的，next数组，如果我们计算字符串下标从1开始，则要给每个PM值加1
设主串为s1s2...sn,模式串p1p2...pn,当主串中第i个字符与模式串中第j个字符发生失配时假设此时应与模式串中第k(k<j)个字符进行比较，则模式串中第k-1个字符必须满足下列条件，且不可能存在k'>k满足下列条件p1p2...pk-1=pj-k+1pj-k+2...pj-1
若存在满足如上条件的子串，则发生失配时，将模式串向右滑动至模式串第k个字符和主串第i个字符对齐，此时模式串中前k-1个字符的子串必定与主串中第i个字符之前的长度为k-1的子串相等
若模式串已匹配相等字符序列中不存在满足上述条件的子串时(视作k=1)，将字符串右移j-1位，让主串第i个字符和模式串第一个字符比较，此时右移位数最大
当模式串第一个字符与主串第i个字符失配，规定next[1]=0,将模式串右移一位，从主串的第i+1位与模式串的第一个字符进行比较
由此得出next函数公式为
下面令p1p2...pk-1为公式1，pj-k+1pj-k+2...pj-1=a为公式2
根据函数公式求解aaaab的next数组步骤如下
带入公式next[1] = 0
1<k<2，此时k没有值,满足其他情况，next[2]=1
1<k<3,则k取2，此时公式1为a,公式2为a，公式1=公式2，所以next[3]=k=2
1<k<4
当k取2时，公式1为a，公式2为a，公式1等于公式3，在看k等于3时
当K取3时，公式1为aa，公式2为aa，公式1等于公式2，此时满足条件2，要取max(k)，所以next[4]=k=3
1<k<5
当k取2时，公式1为a，公式2为a，公式1等于公式2
当k取3时，公式1为aa，公式2为aa，公式1等于公式2
当k取4时，公式1为aaa，公式2为aaa，公式1等于公式2，取最大k，所以next[5]=4
可以参考https://www.bilibili.com/video/BV16X4y137qw
next[1] = 0;
设next[j] = k,此时k满足next函数第二种情况，此时求取next[j+1]=?
情况1：
如果pk=pj,则此时p1p2...pk=pj-k+1pj-k+2...pj，则此时next[j+1]=k+1=next[j]+1
情况2：
如果pk不等于pj，则p1p2...pk不等于pj-k+1pj-k+2...pj
此时将next函数值视为一个模式匹配问题，用前缀p1...pk和后缀pj-k+1...pj匹配，当pk不等于pj,应该将p1...pk向右滑动至第next[k]个字符继续与pj比较，若pnext[k]与pj还是不匹配，则需要找到长度更短的相等前后缀，继续使用pnext[next[k]]与pj比较，直到找到某个更小的k'=next[next...[k]] (1<k'<k<j)，满足条件pk=pj,则此时p1p2...pk=pj-k+1pj-k+2...pj，则next[j+1] = k'+1
如下所示
求next[7],因为next[6] = 3,p6不等于p3，因为next[3] = 1,所以比较p6不等于p1，因为p1,所以p7=1
求next[8],因为next[7]=1,p7=p1,所以next[8]=next[7]+1=2
求next[9],因为next[8]=2,p8=p2,所以next[9]=next[8]+1=3
还有一种情况时从next[0]=-1开始使用，二者区别见KMP算法里面的next数组：对于索引到底是从0还是1开始的分析(基于荣政版数据结构与算法分析)_kmp索引从1开始和从0开始-CSDN博客
next[0] = -1 的目的是方便处理算法中的边界条件，尤其是当模式串的第一个字符与文本中的字符不匹配时，可以直接通过 j = next[j] 进行回溯，此时 j 初始为1，回溯至0时，next[0] 的值为-1可以帮助快速识别出这是回溯的边界，无需进一步移动。next[1] = 0 则是直接表明模式串的第一个字符没有有效前缀，因此没有匹配的信息可以利用。这种方式下，当遇到不匹配时，直接从模式串的第二个字符开始重新尝试匹配，逻辑上更为直接明了。void computeNextWithMinusOne(SString* pattern, int* next) {
int i = 0, j = -1;
next[0] = -1;
while (i < pattern->length) {
if (j == -1 || pattern->str[i] == pattern->str[j]) {
i++; j++;
next[i] = j;
}
else {
j = next[j];
}
}
}
void computeNextWithZero(SString* pattern, int* next) {
int i = 1, j = 0;
next[1] = 0;
while (i < pattern->length) {
if (j == 0 || pattern->str[i] == pattern->str[j]) {
i++; j++;
next[i] = j;
}
else {
j = next[j];
}
}
}
展示一个求解过程如下
int KMPMatchWithMinusOne(SString* str, SString* pattern, int* next) {
int i = 0, j = 0;
while (i < str->length && j < pattern->length) {
if (j == -1 || str->str[i] == pattern->str[j]) {
i++; j++;
}
else {
j = next[j];
}
}
if (j == pattern->length) {
printf("\nPattern found at index: %d\n", i - j);
}
else {
printf("\nPattern not found.\n");
}
}
void KMPMatchWithZero(SString* str, SString* pattern, int* next) {
int i = 0, j = 0; // i是主串位置，j是模式串位置
while (i < str->length && j < pattern->length) {
if (str->str[i] == pattern->str[j]) {
i++;
j++;
}
else {
if (j != 0) {
j = next[j];
}
else {
i++;
}
}
}
if (j == pattern->length) {
// 匹配成功，返回起始位置
printf("\nPattern found at index: %d\n", i - j);
}
else {
printf("\nPattern not found.\n");
}
}
#include <stdio.h>
#include <stdlib.h>
/*
* 默认下标都从0开始
*/
typedef struct {
char str[255];
int length;
}SString;
void computeNextWithMinusOne(SString* pattern, int* next) {
int i = 0, j = -1;
next[0] = -1;
while (i < pattern->length) {
if (j == -1 || pattern->str[i] == pattern->str[j]) {
i++; j++;
next[i] = j;
}
else {
j = next[j];
}
}
}
void computeNextWithZero(SString* pattern, int* next) {
int i = 1, j = 0;
next[1] = 0;
while (i < pattern->length) {
if (j == 0 || pattern->str[i] == pattern->str[j]) {
i++; j++;
next[i] = j;
}
else {
j = next[j];
}
}
}
int KMPMatchWithMinusOne(SString* str, SString* pattern, int* next) {
int i = 0, j = 0;
while (i < str->length && j < pattern->length) {
if (j == -1 || str->str[i] == pattern->str[j]) {
i++; j++;
}
else {
j = next[j];
}
}
if (j == pattern->length) {
printf("\nPattern found at index: %d\n", i - j);
}
else {
printf("\nPattern not found.\n");
}
}
void KMPMatchWithZero(SString* str, SString* pattern, int* next) {
int i = 0, j = 0; // i是主串位置，j是模式串位置
while (i < str->length && j < pattern->length) {
if (str->str[i] == pattern->str[j]) {
i++;
j++;
}
else {
if (j != 0) {
j = next[j];
}
else {
i++;
}
}
}
if (j == pattern->length) {
// 匹配成功，返回起始位置
printf("\nPattern found at index: %d\n", i - j);
}
else {
printf("\nPattern not found.\n");
}
}
void testWithZero() {
SString str = { "aaabaaaab",9 };
SString pattern = { "aaaab",5 };
int* next = (int*)malloc((pattern.length + 1) * sizeof(int));
computeNextWithZero(&pattern, next);
for (int i = 1; i <= pattern.length; i++) {
printf("%d ", next[i]);
}
KMPMatchWithZero(&str, &pattern, next);
}
void testWithMinusOne() {
SString str = { "aaabaaaab",9 };
SString pattern = { "aaaab",5 };
int* next = (int*)malloc((pattern.length + 1) * sizeof(int));
computeNextWithMinusOne(&pattern, next);
for (int i = 0; i < pattern.length; i++) {
printf("%d ", next[i]);
}
KMPMatchWithMinusOne(&str, &pattern, next);
}
int main() {
testWithZero();
testWithMinusOne();
return 0;
}
模式aaaab在和主串aaabaaaaab进行匹配时，next数组如下
在第一次对比时，在i=3，j=3时，主串的b不等于模式串的a
按照kmp算法，向后移动位数=已匹配字符数-对应部分的匹配值=3-2=1，但是我们观察到此时模式串的前4个字符都是相同的，按照next数组的PM值，就多余要进行3次比较
这时因为,当pj不等于si时，下次比较就是pnext[j]和si比较，当pj=pnext[j]时，pnext[j]也肯定是不等于si的，这样的比较就是多余的，此时需要优化next数组，递归遍历将next[j]修正为next[next[j]]，一直到pj不等于pnext[j]为止
优化后next求解代码如下
void computeNextWithMinusOne(SString* pattern, int* next) {
int i = 0, j = -1;
next[0] = -1;
while (i < pattern->length) {
if (j == -1 || pattern->str[i] == pattern->str[j]) {
i++; j++;
if (pattern->str[i] != pattern->str[j]) {
next[i] = j;
}
else {
next[i] = next[j];
}
}
else {
j = next[j];
}
}
}
void computeNextWithZero(SString* pattern, int* next) {
int i = 1, j = 0;
next[1] = 0;
while (i < pattern->length) {
if (j == 0 || pattern->str[i] == pattern->str[j]) {
i++; j++;
if (pattern->str[i] != pattern->str[j]) {
next[i] = j;
}
else {
next[i] = next[j];
}
}
else {
j = next[j];
}
}
}