// SString.h - 串
#include <iostream>

#define MAXLEN 255

/*********************************************************************************************************************************
 * 数据类型一览
 * SString 定长顺序存储（静态数组）
 * HString 串的顺序存储 可拓展长度顺序存储（指针数组）
 * StringNode, *Node 串的链式存储
 * 
 * 操作函数 共享栈操作在函数名后加0或者1 不带头结点的链栈操作在函数名后加WithoutFirstNode
 * bool StrAssign(&T, *ch) 赋值操作，将字符串ch复制到串T中 正常结束返回1，否则返回0
 * bool StrCopy(&T, S) 复制操作，将S串复制到串T中 正常结束返回1，否则返回0
 * bool StrEmpty(S) 判空 空返回1，否则返回0
 * int StrLength(S) 求长度 返回串的长度
 * bool ClearString(S) 清空 正常结束返回1，否则返回0
 * bool DestroyString(&S) 销毁 正常结束返回1，否则返回0
 * bool Concat(&T, S1, S2) 串连接,将S1和S2连接后存入T 正常结束返回1，否则返回0
 * bool SubString(&Sub, S, pos, len) 求子串，求出串S中位于pos位置的长度为len长度的子串存入Sub 正常结束返回1，否则返回0
 * int StrCompare(S, T) 比较操作 比较串S和T的大小，返回值小于0，等于0，大于0，分别表示S<T，S=T，S>T
 * int Index(S, T) 定位操作，求出串S中第一次出现串T的位置 返回值为定位串T的位置，如果没有找到返回0
 * int Index2(S, T) 朴素模式匹配，求出串S中第一次出现串T的位置 返回值为定位串T的位置，如果没有找到返回0
 * void get_next(T, next) 求模式串T的next数组
 * void get_nextval(T, nextval) 求模式串优化后的nextval数组
 * int Index_KMP(S, T) KMP算法求出串S中第一次出现串T的位置 返回值为定位串T的位置，如果没有找到返回0
 * 
 *********************************************************************************************************************************/

// 串的顺序存储 定长顺序存储（静态数组）
typedef struct SString{
    char ch[MAXLEN];  // 每个分量存储一个字符
    int length;  // 串的实际长度
}SString;

// 串的顺序存储 可拓展长度顺序存储（指针数组）
typedef struct HString{
    char *ch;  // 按串长分配存储区，ch指向串的基地址
    int length;  // 串的长度
}HString;
//HString S; S.ch = (char *)malloc(MAXLEN*sizeof(char)); S.length = 0;

// 串的链式存储
typedef struct StringNode{
    char ch;  // 每个结点存1字符，若要提高存储密度，则可设置为多个字符数组
    struct StringNode *next;
}StringNode, *Node;

// 赋值操作
bool StrAssign(SString &T, char *ch){
    int i = 1;
    while(ch[i] != '\0'){
        T.ch[i] = ch[i];
        i++;
    }
    T.length = i;
    return true;
}

// 复制操作
bool StrCopy(SString &T, SString S){
    int i = 1;
    while(S.ch[i] != '\0'){
        T.ch[i] = S.ch[i];
        i++;
    }
    T.length = i;
    return true;
}

// 判空
bool StrEmpty(SString S){
    return S.length == 0;
}

// 求长度
int StrLength(SString S){
    return S.length;
}

// 清空
bool ClearString(SString &S){
    S.length = 0;
    return true;
}

// 销毁
bool DestroyString(SString &S){
    S.length = 0;
    return true;
}

// 串连接
bool Concat(SString &T, SString S1, SString S2){
    int i = 1;
    while(S1.ch[i] != '\0'){
        T.ch[i] = S1.ch[i];
        i++;
    }
    while(S2.ch[i] != '\0'){
        T.ch[i] = S2.ch[i];
        i++;
    }
    T.length = i;
    return true;
}

// 求子串
bool SubString(SString &Sub, SString S, int pos, int len){
    if(pos < 1  pos > S.length  len < 0  len > S.length - pos + 1){  // 子串位置不合法
        return false;
    }
    Sub.length = len;
    for(int i = 0; i < len; i++){
        Sub.ch[i] = S.ch[pos - 1 + i];
    }
    return true;
}

// 比较操作
int StrCompare(SString S, SString T){
    for(int i = 0; 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(SString S, SString T){
    int i = 1, n = S.length, m = T.length;
    SString Sub;
    while(i <= n - m + 1){
        if(SubString(Sub, S, i, m) && StrCompare(Sub, T) == 0){
            return i;
        }
        i++;
    }
}

// 朴素模式匹配
int Index2(SString S, SString T){
    int k = 1;  // 当前匹配的字符位置
    int i = k, j = 1;
    while(i <= S.length && j <= T.length){
        if(S.ch[i] == T.ch[j]){
            i++;  // 继续比较后续字符
            j++;
        }else{
            k++;  // 匹配失败，向后移动匹配字符位置
            i = k;
            j = 1;
        }
    }
    if(j > T.length){
        return k;
    }else{
        return 0;
    }
}

// KMP算法：朴素模式算法优化
int Index_KMP_Need_Next(SString S, SString T, int next[]){  // 传入next数组
    // 例：google的next数组为next[7] = {0, 0, 1, 1, 1, 2, 1}
    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都加一以至于可以i向后移，j归为1
            i++;
            j++;
        }else{
            j = next[j];
        }
    }
    if(i > T.length){
        return i-T.length;
    }else{
        return 0;
    }
}

// 求模式串T的next数组
void get_next(SString T, int next[]){
    int i = 0, j = 0;
    next[1] = 0;
    while(i < T.length){
        if(j == 0  T.ch[i] == T.ch[j]){
            ++i;
            ++j;
            // 若pi等于pj，则next[j+1] = next[j] + 1
            next[i] = j;
        }else{
            j = next[j];
        }
    }
}

// next数组优化为nextval数组
void get_nextval(SString T, int nextval[]){
    int *next = new int[T.length+1];
    get_next(T, next);
    nextval[1] = 0;
    for(int j = 2; j <=T.length; j++){
        if(T.ch[j] == T.ch[next[j]]){
            nextval[j] = nextval[next[j]];
        }else{
            nextval[j] = next[j];
        }
    }
    delete[] next;
}

// KMP算法
int Index_KMP(SString S, SString T){
    int i = 1, j = 1;
    int *next = new int[T.length+1];
    get_next(T, next);  // 求模式串T的next数组 时间复杂度O(m)
    while(i <= S.length && j <= T.length){  // 时间复杂度O(n)
        if(j == 0  S.ch[i] == T.ch[j]){
            i++;
            j++;  // 继续比较后继字符
        }else{
            j = next[j];  // 模式串向右移动
        }
    }
    delete[] next;
    if(j>T.length){
        return i-T.length;  // 匹配成功返回匹配的位置
    }else{
        return 0;
    }
}