#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码 */
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
//串的存储方式有三种 定长顺序存储 堆分配存储 块链存储

//串的定长顺序存储  一组地址连续的存储单元存储串值的字符序列
#define MAXSTRLEN 100 //可以定义的最大
typedef unsigned char SString[MAXSIZE+1];

//串的堆分配存储表示 一组地址连续的存储单元存储串值的字符序列，但是动态分配串值的空间
//在定长顺序存储中，如果操作中出现串的序列值超过MAXSIZE,会使用截尾法操作
//为了克服这个弊端，只有不限定串长的长度，即动态分配空间
//即采取了 串的第二种表现方式 堆分配存储表示
//一组地址连续的，内存是动态分配得到的
typedef struct {
    char *ch;
    int length;
}HString;

//串的块链存储表示  链表方式存储串值，每个节点称为块，整个链表称为块链
//特点，存储量大且操作复杂
//每个结点既可以存放一个字符，也可以存放多个字符。每个结点存多个字符时，没有字符的位置用'#'或'\0'补足（不满补足）
//结点大小越小，相关操作的实现越方便，但存储密度下降
//不如前俩种的结构灵活，操作简单
#define CHUNKSIZE 80 //可定义的块大小
typedef struct Chunk{ //节点===块
    char ch[CHUNKSIZE];
    struct Chunk *next;
};
typedef struct {
    struct Chunk *head,*tail; //串的头尾指针
    int curlen; //串的当前长度
}LString;
//定长顺序存储的 操作集合
Status Concat(SString T,SString S1,SString S2);
Status SubString(SString T,SString S,int pos,int len);
//以下为堆分配的操作集合
void StrAssign(HString *H,char *s);
int StrLength(HString H);
int StrCompare(HString s1,HString s2);
void ClearStr(HString *H);
Status Concat1(HString *H,HString s1,HString s2);
HString SubString1(HString H,int pos,int len);
Status  StrCopy(HString *s1,HString s2);
Status  StrInsert(HString *s1,int pos,HString s);
//模式匹配
int Index(SString S,SString T,int pos){
    //返回字串T在主串S中 指定pos之后的位置
    int i=pos,j=1;
    while(i<=S[0] && j<=T[0]){
        if(S[i]==T[j]){
            i++;
            j++;
        } else{
            i=i-j+2;
            j=1;
        }
    }
    if(j>T[0])
        return i-T[0];
    return 0;
}
//Kmp next数组的获得
void Get_next(SString S,int next[]){
    int i=1,j=0;//初始化，i相当于主串的指针，j相当于字串
    next[1]=0;//初始化 next[1]=0
    while(i<S[0]){ //i符合的条件
        if(j==0 || S[i]==S[j]){   //当j为0 或者 字符匹配时，i,j指针自增
            i++;
            j++;
            next[i]=j;  //同时给next[i]赋值
        } else {
            j=next[j]; //否则移动j指针
        }
    }
}

//当主串为aaaaaab时，字串为aab，其中有大量重复的值时候，kmp就显得低下了
//所以对kmp的next数组进行改进  相同的值的next数组赋值为0
void Get_nextval(SString S,int next[]){
    int i=1,j=0;//初始化，i相当于主串的指针，j相当于字串
    next[1]=0;//初始化 next[1]=0
    while(i<S[0]){ //i符合的条件
        if(j==0 || S[i]==S[j]){   //当j为0 或者 字符匹配时，i,j指针自增
            i++;
            j++;
            if(S[i]!=S[j]) next[i]=j; //仅仅判断下一个值是否相等，不相等的话和原来一样
            else{
                next[i]=next[j];//相等的话就和next[1]=0 赋初值为0，相同元素的next[]数组都是0
            }
        } else {
            j=next[j]; //否则移动j指针
        }
    }
}

int Index_KMP(SString S,SString T,int pos){
    //返回字串T在主串S中 指定pos之后的位置
    //一开始和暴力匹配算法一样
    int i=pos,j=1,next[T[0]];//创建next数组
    Get_next(T,next);//给next数组赋值
    while(i<=S[0] && j<=T[0]){
        if(S[i]==T[j] || j==0){ //和求next[]数组一样
            i++;
            j++;
        } else{
            //这里i 不变，只变化了j的指针，有next[]数组确定
           j=next[j];
        }
    }
    if(j>T[0])
        return i-T[0];
    return 0;
}

int main() {
    printf("Hello, World!\n");

    if(0==1){
        //定长顺序存储 用一组地址连续的存储单元存储串值的字符序列
        //串的表现方式 1 下标为0的放串的实际长度，2，串尾加入'\0',此时串长为隐藏值，不利于操作
        //所以我们使用下标为0的存放串的实际长度的表现方式
        printf("串的定长顺序存储 实现连接，和求子串\n");
        SString s1={3,'a','b','c'};
        SString s2={4,'e','d','f','g'};
        printf("s1为 %s\n",s1+1);
        printf("s2为 %s\n",s2+1);
        printf("s2的长度 %d\n",strlen(s2));
        SString T,sub,T1;
        Concat(T,s1,s2);
        printf("合并之后的T为 %s\n",T+1);
        SubString(sub,T,3,3);
        printf("取T的字串，从第3个位置，长度为3的字串sub 为%s \n",sub+1);
        printf("sub的长度 %d\n",sub[0]);
        Concat(T1,T,s2);
        printf("截尾法输出T1= T+s2\n");
        printf("合并之后的T1为 %s\n",T1+1);


    }
    SString T={5,'a','b','c','a','c'};
    SString S={13,'a','b','a','b','c','a','b','c','a','c','b','a','b'};
    if(0==1){
        printf("串的模式匹配  采取第一种 定长顺序存储\n");

        printf("字串T %s\n ",T+1);
        printf("主串S %s\n",S+1);
        printf("串的模式匹配  采取第1个位置开始的\n");
        printf("位置为%d ",Index(S,T,1));

    }
    if(1==1){
        //改进点  减少指针回溯，即向右滑动，距离的大小(确定)
        printf("\n串的模式匹配的改进算法，KMP算法\n");
        printf("字串T %s\n ",T+1);
        printf("主串S %s\n",S+1);
        printf("串的模式匹配  采取第1个位置开始的\n");
        printf("位置为%d ",Index_KMP(S,T,1));

    }
    return 0;
}
//把S1和S2 连接放到T 定长顺序存储的
Status Concat(SString T,SString S1,SString S2){
    if(S1[0]+S2[0]<=MAXSIZE) {
        T[0]=S1[0]+S2[0];
        for (int i = 1; i <=S1[0] ; ++i) {
            T[i]=S1[i];
        }
        for (int j =S1[0]+1 ; j <=S1[0]+S2[0] ; ++j) {
            T[j]=S2[j-S1[0]];
        }
        return TRUE;
    } else if (S1[0]<MAXSIZE){
        for (int i = 1; i <=S1[0] ; ++i) {
            T[i]=S1[i];
        }
        for (int j =S1[0]+1 ; j <=MAXSIZE ; ++j) {
            T[j]=S2[j-S1[0]];
        }
        return FALSE;
    } else{
        for (int i = 1; i <=MAXSIZE ; ++i) {
            T[i]=S1[i];
        }
        return FALSE;
    }
}
Status SubString(SString T,SString S,int pos,int len){
    if(pos<0 || pos>S[0] || len<1 || len >S[0]-pos+1)
        return FALSE;
    T[0]=len;
    for (int i = 1; i <=len ; ++i) {
        T[i]=S[pos+i-1];
    }
    T[len+1]='\0';
    return TRUE;
}


//以下为堆分配的操作集合
void StrAssign(HString *H,char *s){
    int len=strlen(s);
    // 求长度的原型代码
    char *c;
    int i;
    for (i = 0,c=s; c; ++i,c++) {

    }
    printf("%d \n",i);
    if(H->ch) free(H->ch);
    if(len==0){
        H->ch=NULL;
        H->length=0;
    }
    H->ch=(char*)malloc(len*sizeof(char));
    H->length=len;
    //原理上是和定长顺序一样，一个一个赋值完成的，原型代码就不再给出
    strcpy(H->ch,s);
}
int StrLength(HString H){
    return H.length;
}
int StrCompare(HString s1,HString s2){
    return strcmp(s1.ch,s1.ch);
    //本质上是 某个不相同的元素的差，否则就return 0了(默认)
    /**
     *   for(;;){
             if(s1.ch[i]!=s2.ch[i])
             return s1.ch[i]-s2.ch[i];
        }
     */

}
void ClearStr(HString *H){
    if(H->ch) {
        free(H->ch);
        H->length=0;
        H->ch=NULL;
    }

}
Status Concat1(HString *H,HString s1,HString s2){
    //和 定长顺序存储一样
    H->length=s1.length+s2.length;
    H->ch=(char*)malloc(H->length*sizeof(char));
    for (int i = 0; i <H->length ; ++i) {
        if(i<s1.length){
            H->ch[i]=s1.ch[i];
        } else{
            H->ch[i]=s2.ch[i-s1.length];
        }
    }
}
HString SubString1(HString H,int pos,int len){
    HString s;
    s.length=len;
    s.ch=(char*)malloc(s.length* sizeof(char));
    for (int i = 0; i <s.length ; ++i) {
        s.ch[i]=H.ch[pos+i];
    }
    return s;
}
Status  StrCopy(HString *s1,HString s2){
    if(s1->ch){
        free(s1->ch);
        s1->length=0;
        s1->ch=NULL;
    }
    s1->length=s2.length;
    s1->ch=(char*)malloc(s1->length* sizeof(char));
    for (int i = 0; i <s1->length ; ++i) {
        s1->ch[i]=s2.ch[i];
    }
}
Status  StrInsert(HString *s1,int pos,HString s){
    if(pos<1 || pos>s1->length )
        return FALSE;
    for (int i = s1->length+s.length; i >=pos ; i--) {
        s1->ch[i]=s1->ch[i-s.length];
    }
    for (int j =pos; j <pos+s.length+1 ; ++j) {
        s1->ch[j]=s.ch[j-pos];
    }
}