using namespace std;
#include <iostream>
#include<string>

//自定义字符串存储结构String（包括char数组、length长度）
#define maxlen 20
typedef struct {  
    char ch[maxlen];
    int length;
}String;

//初始化s
void strInit(String& s) {
    s.length = 0;
    s.ch[0] = s.length; //ch[0]空着用来存长度，初始化为0
}

//s判空
bool strEmpty(String s) {
    if (s.length == 0) //如果长度为0代表空串
        return true;
    else
        return false;
}

//获得s长度
int strLength(String s) {
    cout << "长度打印：" << s.length << endl;;
    return s.length; //或者s.ch[0]
}

//将string字符串赋值到s数据结构中用char数组保存
String strAssign(String &s, string t) {
    int i = 1; //从1开始存字符，0空着用来存长度
    s.length =0;
    cout << "字符串打印：";
    for (int j = 0; j < t.length(); j++) {
        s.ch[i] = t[j];
        cout << s.ch[i] << " ";
        s.length++;
        i++;
    }
    s.ch[0] = s.length; //0空着用来存长度
    cout << endl;
    return s;
}

/////////上面都是一些基础函数，下面开始KMP算法/////////////////////////////////////////////
//step1:求出子串的next[j]值【普通版】
void get_next(String s, int next[]) {
    int j = 1, k = 0;
    next[1] = 0; //next[1]值必须填0
    while(j<s.length){
        if (s.ch[j] == s.ch[k] || k == 0) {
            j++;
            k++;
            next[j] = k;
        }
        else
            k = next[k];
    }
    //打印看看
    cout <<"打印next[i]为： ";
    for (int i = 1; i <=s.length; i++)
        cout << next[i] << " ";
    cout << endl;
}

//step1:求出子串的nextval[j]值【改进版,只记录不相同值的索引，避免j的无效回退。2个方法2选1即可】
void get_nextval(String s, int nextval[]) {
    int j = 1, k = 0;
    nextval[1] = 0; //nextval[1]值必须填0
    while (j < s.length) {
        if (s.ch[j] == s.ch[k] || k == 0) {
            j++;
            k++;
            if (s.ch[j] != s.ch[k])
                nextval[j] = k;
            else
                nextval[j] = nextval[k];
        }
        else
            k = nextval[k];
    }
    //打印看看
    cout << "打印nextval[i]为： ";
    for (int i = 1; i <= s.length; i++)
        cout << nextval[i] << " ";
    cout << endl;
}

//step2:开始主串中匹配子串，并返回第一个元素出现的位置
int index3(String s, String t, int next[]) {
    int i = 1, j = 1;
    while (i <= s.length && j <= t.length) { //找到最后一个字符为止
        if (j == 0||s.ch[i] == t.ch[j]) { //如果字符不相同或者j为0了，i和j同步往后移1位
            i++;
            j++;
        }
        else
            j = next[j]; //j回退到next[j]位置
    }//while结束，s和t至少有一个找到头了
    if (j > t.length) {
        //打印看看
        cout << "index3打印子串为： ";
        for (int m = i - t.length; m < i; m++)
            cout << s.ch[m] << " ";
        cout << endl;
        return (i - t.length); //或者i-t.length，返回i最开始的位置
    }
    else
        return 0;
}

void main() {
    int next[20];
　 int nextval[20];
　 string sf = "aaaacabcaaaabab";
　 string sz = "aaaab";

    String ss ,tt;
    strInit(ss); //初始化主串
    strInit(tt); //初始化子串
    strAssign(ss, sf);  //把字符串放进数据结构
    strAssign(tt, sz);  //把字符串放进数据结构
    strLength(ss); //获取长度
    strLength(tt); //获取长度

    get_next(tt, next); //获得子串各个next值
    cout << "用next的index3 i下标：" << index3(ss, tt, next) << endl;
    
    get_nextval(tt, nextval); //获得子串各个nextval值
    cout << "用nextval的index3 i下标：" << index3(ss, tt, nextval) << endl;
}