// 0号位置不存元素，使数组下标与字符串位置保持一致
#include "./Head/StringData.h"
#include "./Source/StringCommon.cpp"
#include "./Source/StringFunction.cpp"int main() {SqString String;// 初始化InitString(String);char Str[] = "abascbascabaaba";CreateString(String, Str);// KMPSqString Sub;// 初始化InitString(Sub);char Str1[] = "abaaba";CreateString(Sub, Str1);int next[Sub.Length + 1];GetNext(Sub, next);//    int nextval[Sub.Length + 1];
//    GetNextval(Sub, nextval);// 输出for (int i = 1; i <= Sub.Length; i++) {printf("%3d", next[i]);}printf("\\n");int pos = IndexKMP(String, Sub, next);printf("pos = %d\\n", pos);return 0;
}

//
// Created by 24955 on 2023-03-21.
// 0号位置不存元素，使数组下标与字符串位置保持一致
//#ifndef INC_01_SQSTRING_STRINGDATA_H
#define INC_01_SQSTRING_STRINGDATA_H
// 头文件
#include <stdio.h>
#include <stdlib.h>// 常量
#define MaxSize 30
typedef char ElemType;// 结构体-顺序存储
typedef struct {ElemType ch[MaxSize];int Length;
} SqString;
#endif //INC_01_SQSTRING_STRINGDATA_H

//
// Created by 24955 on 2023-03-21.
// 0号位置不存元素，使数组下标与字符串位置保持一致
//
// 初始化串
void InitString(SqString &String) {String.Length = 0;
}// 创建串
void CreateString(SqString &String, char Str[]) {for (int i = 1; Str[i - 1] != '\\0'; i++) {String.ch[i] = Str[i - 1];String.Length++;}
}// 判断字符串是否为空
bool StrEmpty(SqString String) {if (String.Length == 0) {return true;}return false;
}// 串输出
void StringPrint(SqString String) {if (StrEmpty(String)) {return;}for (int i = 1; i <= String.Length; i++) {printf("%c", String.ch[i]);}printf("\\n");
}

//
// Created by 24955 on 2023-03-21.
// 0号位置不存元素，使数组下标与字符串位置保持一致
//
// KMP优化-nextval数组
void GetNextval(SqString Sub, int nextval[]) {/ 1. 模式串相同元素取消重复匹配* 2. next[i] = next[next[j]]*/nextval[1] = 0;// 0号位置不存元素，使数组下标与字符串位置保持一致int i = 1, j = 0;while (i <= Sub.Length) {if (j == 0 || Sub.ch[i] == Sub.ch[j]) {i++;j++;if (Sub.ch[i] != Sub.ch[j]) {nextval[i] = j;} else {nextval[i] = nextval[j];}} else {j = nextval[j];}}
}// next和i、j过程
{/* next* 1. 0 1* 2. j = next[1]; // 0* 3. 0 1 1* 4. 0 1 1 2* 5. j = next[2]; // 1* 6. 0 1 1 2 2* 7. 0 1 1 2 2 3* 8. 0 1 1 2 2 3 4*/
/* abaaba* 1. i = 2;j = 1;* 2. i = 2;j = 0;* 3. i = 3;j = 1;* 4. i = 4;j = 2;* 5. i = 4;j = 1;* 6. i = 5;j = 2;* 7. i = 6;j = 3;* 8. i = 7;j = 4;*/}
// 求next数组
void GetNext(SqString Sub, int next[]) {next[1] = 0;// 0号位置不存元素，使数组下标与字符串位置保持一致// Sub.ch[0] = '\\0';、Sub.ch[1] = 'a';int i = 1, j = 0;while (i <= Sub.Length) {if (j == 0 || Sub.ch[i] == Sub.ch[j]) {i++;j++;next[i] = j;} else {j = next[j];}}
}// 求子串位置-时间复杂度O(m*n)
int IndexKMP(SqString S, SqString Sub, int next[]) {/ 1. i不回溯，j按next值回溯*/int i = 1, j = 1;while (i <= S.Length && j <= Sub.Length) {if (j == 0 || S.ch[i] == Sub.ch[j]) {i++;j++;} else {j = next[j];}}if (i <= S.Length + 1) {return i - j + 1;}return 0;
}