#include <stdio.h>
#define MAX_LENGTH 100
/*
* 主题：串的朴素模式匹配算法
* 作者：熊猫大大
* 时间：2020-01-15
*/

//字符串结构体
typedef struct {
    char content[MAX_LENGTH];//内容部分，最后一位存储'\0',所以实际字符串内容长度是MAX_LENGTH-1
    int length;//实际长度
}String;

//打印字符串
void printStr(String *str)
{
    printf("str:%s\n", str->content);
}

//请空字符串
void clearStr(String *str)
{
    str->content[0] = '\0';
    str->length = 0;
}

//返回字符串长度
int getStrLength(String *str)
{
    return str->length;
}

//判断字符串是否为空 是1 否0
int isEmpty(String *str)
{
    if (str->length == 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

//添加字符
int appendChar(String *str, char c)
{
    if (str->length < MAX_LENGTH - 1)
    {
        str->content[str->length] = c;
        str->length++;
        str->content[str->length] = '\0';
        return 1;
    }
    else //长度不足，返回失败0
    {
        return 0;
    }
}

//插入字符,index从0开始,注意需要将后面的字符全部向后挪一个位置
int insertChar(String *str, int index, char c)
{
    int i;
    if (str->length < MAX_LENGTH - 1)
    {
        for (i = str->length; i >= index; i--) //从最后一个'\0'开始都向后移动一个位置
        {
            str->content[i + 1] = str->content[i];
        }
        str->content[index] = c;//将插入元素放入指定位置
        return 1;
    }
    else //长度不足，返回失败0
    {
        return 0;
    }
}

//删除指定位置元素，index从0开始，直接从后面往前覆盖即可
int deleteChar(String *str, int index)
{
    int i;
    for (i = index; i <= str->length; i++)
    {
        str->content[i] = str->content[i + 1];
    }
    return 1;
}

//将str2连接到str1
int concat(String *str1, String *str2)
{
    int i = 0;
    int leftLength = MAX_LENGTH - 1 - str1->length;//剩余可用长度
    if (leftLength < str2->length) {//长度不足返回失败
        return 0;
    }
    //依次取出str2中元素追加到str1
    for (i = 0; i < str2->length; i++)
    {
        appendChar(str1, str2->content[i]);
    }
    return 1;
}

// 朴素模式匹配，返回值-1匹配失败，其他返回值为匹配成功的起始位置
int index(String *str1, String *str2) {
    int position = 0;//从主串0位置开始
    int i = 0;
    while (position < str1->length) {
        for (i = 0; i < str2->length; i++) {//匹配子串
            if (position + i > str1->length - 1) {
                break;
            }
            if (!(str1->content[position + i] == str2->content[i])) {
                break;
            }
        }
        if (i == str2->length) {//全部走完没跳出，匹配成功
            return position;
        }
        position++;
    }
    return -1;
}

int main()
{
    // 定义str1
    String str1;
    clearStr(&str1);
    appendChar(&str1, 'a');
    appendChar(&str1, 'b');
    appendChar(&str1, 'c');
    appendChar(&str1, 'd');
    printf("str1:\n");
    printStr(&str1);
    // str2测试
    String str2;
    clearStr(&str2);
    appendChar(&str2, 'b');
    appendChar(&str2, 'c');
    appendChar(&str2, 'd');
    printf("str2:\n");
    printStr(&str2);
    // 模式匹配
    printf("匹配结果：%d\n",index(&str1, &str2));

}