#define MAX_SIZE 1024

typedef struct {
    char memory[MAX_SIZE];	//串的内存
    int cur_size;  //当前串的大小
} STR, *LPSTR;

//创建一个串
LPSTR CreateStr(const char* str) {
    //开内存
    LPSTR p_str = (LPSTR)malloc(sizeof(STR));
    //防止'\0'的问题,这里我选择全初始化为'\0'
    for (int i = 0; i < MAX_SIZE; ++i) {
        p_str->memory[i] = '\0';
    }
    //形参拷贝到串的内存
    int count = 0;  //串的长度
    while (str[count] != '\0') {
        p_str->memory[count] = str[count];
        count++;
    }
    //更新串的长度
    p_str->cur_size = count;
    return p_str;
}

//串的插入(在当前串插入多个元素)
//pos是数组下标,这里写的是在pos的下一个位置进行插入
void InsertStrByPos(LPSTR p_str, const char* str, int str_len, int pos) {
    //插在下标前面做减操作
    // pos -= 1;
    if (pos < 0 || pos >= MAX_SIZE) {
        printf("下标有误,无法插入\n");
        return;
    }
    //大于数组容量
    if (p_str->cur_size + str_len >= MAX_SIZE) {
        printf("超出串的容量,无法插入\n");
        return;
    }
    //插在原来串的后面
    if (pos > p_str->cur_size) {
        for (int i = 0; i < str_len; ++i) {
            p_str->memory[p_str->cur_size++] = str[i];
        }
    } else {
        //腾位置
        //从最后一个元素开始挪动(p_str->cursize - 1)
        for (int i = p_str->cur_size - 1; i >= pos; i--) {
            p_str->memory[str_len + i] = p_str->memory[i];
        }
        //插入新串
        for (int i = 0; i < str_len; ++i) {
            p_str->memory[pos + i] = str[i];
        }
        p_str->cur_size += str_len;
    }
}

void DeleteStrByIndex(LPSTR p_str, int start_idx, int end_idx) {
    if (start_idx <= 0 || start_idx > end_idx || end_idx > MAX_SIZE) {
        printf("区间有误,无法删除\n");
        return;
    }
    int count = end_idx - start_idx + 1; //真实的区间元素个数
    //后面的元素往前移动
    for (int i = end_idx, j = start_idx - 1; i < p_str->cur_size; ++i, ++j) {
        p_str->memory[j] = p_str->memory[i];
    }
    //置空后面的元素
    for (int i = p_str->cur_size; i >= p_str->cur_size - count; --i) {
        p_str->memory[i] = '\0';
    }
    p_str->cur_size -= count;
}

//串的打印
void PrintStr(LPSTR p_str) {
    for (int i = 0; i < p_str->cur_size; ++i) {
        printf("%c", p_str->memory[i]);
    }
    putchar('\n');
}

//测试数据
int main(int argc, char* argv[]) {
    LPSTR p_str = CreateStr("ILoveyou");

    PrintStr(p_str);
    printf("p_str->cur_size:%d\n", p_str->cur_size);

    printf("插在原来串的后面:\n");
    InsertStrByPos(p_str, "back", 4, p_str->cur_size);
    PrintStr(p_str);

    printf("插入XXX:\n");
    InsertStrByPos(p_str, "XXX", 3, 2);
    PrintStr(p_str);

    printf("p_str->cur_size:%d\n", p_str->cur_size);

    printf("删除1->3的元素:\n");
    DeleteStrByIndex(p_str, 1, 3);
    PrintStr(p_str);

    printf("p_str->cur_size:%d\n", p_str->cur_size);

    return 0;
}

int BruteForce(LPSTR p_str_one, LPSTR p_str_two) {
    int index = 0;  //临时记录序号,用来返回找到的位置
    int i = 0;
    int j = 0;
    while (p_str_one->memory[i] != '\0' && p_str_two->memory[j] != '\0') {
        if (p_str_one->memory[i] == p_str_two->memory[j]) {
            ++i;
            ++j;
        } else {    //不匹配, 重新从第一个
            ++index;
            i = index;
            j = 0;      //换第二个位置又从父串第一个位置开始比
        }
    }
    if (p_str_two->memory[j] == '\0') {
        return ++index;
    }
    return -1;
}

//测试数据
int main(int argc, char* argv[]) {
    LPSTR p_str1 = CreateStr("abcabcacb");
    LPSTR p_str2 = CreateStr("abcac");
    printf("从第%d个元素开始匹配", BruteForce(p_str1, p_str2));
    return 0;
}

//获取匹配值
void GetNext(LPSTR p_str, int next[]) {
    int len = p_str->cur_size;  //用的是数组下标
    int i = 0;
    int j = -1;
    // 0在这里表示共同元素为0, 有具体的含义,所以初始化为-1了
    next[0] = -1;
    while (i < len) {
        if (j == -1 || p_str->memory[i] == p_str->memory[j]) {
            ++i;
            ++j;
            next[i] = j;  //部分匹配元素的长度
        } else {
            j = next[j];  //重置j为-1
        }
    }
}

int KMP(LPSTR p_str_one, LPSTR p_str_two, int next[]) {
    //第一个得到表
    GetNext(p_str_two, next);
    int i = 0;
    int j = 0;
    while (i < p_str_one->cur_size && j < p_str_two->cur_size) {
        if (j == -1 || p_str_one->memory[i] == p_str_two->memory[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (j == p_str_two->cur_size) {
        return i - j;
    }
    return -1;
}

//测试数据
int main(int argc, char** argv) {
    LPSTR p_str = CreateStr("ABCDABD");
    int next[8];
    GetNext(p_str, next);
    for (int i = 0; i < 8; ++i) {
        printf("%d\t", next[i]);
    }
    putchar('\n');

    LPSTR p_str_one = CreateStr("BBC ABCDAB ABCDABCDABDE");
    LPSTR p_str_two = CreateStr("ABCDABD");
    printf("第%d个元素开始匹配\n", KMP(p_str_one, p_str_two, next));

    putchar('\n');
    return 0;
}