实验内容及要求：

从键盘输入主串s以及子串t1和t2。编写程序，将主串s中所有t1子串替换为t2子串，输出替换后得到的串以及t1被替换的次数。要求子串查找采用改进KMP算法。

实验目的：掌握KMP算法。

数据结构设计简要描述：

采用一个定长数组和一个长度变量组成结构体

// 定义串,最大容量255,第一个位置不放元素

typedef struct {

    char s[256];

    int length;

}SString;

    

算法设计简要描述：

采用kmp算法去匹配t1，未改进的next函数将next值存储到next数组中

输入/输出设计简要描述：

输入：根据提示在键盘上输入主串s、子串t1、子串t2

输入：采用遍历数组的方式将串中所有字符输出

编程语言说明：

使用Visual Studio Code编程。 主要代码采用C语言实现 ；动态存储分配采用C++的new和delete操作符实现；输入与输出采用C++的文件流对象和cout流；程序注释采用C/C++规范。

    

主要函数说明：

// 从键盘录入字符,完成三个串的初始化

void get_str(SString& s, SString& t1, SString& t2);

// kmp算法

int kmp(SString s, SString t, int pos, int next[]);

// 求next值并存入next数组

void Next(SString t, int next[]);

// 替换时主串其他字符移动情况

void move(SString& s, int pos, int dis);

// 输出串所有字符

void print(SString& s);

程序测试简要报告：

1. 测试实例1

程序输入

s：aaaaaaa

t1：aa

t2：abc

程序输出

结论

程序输出结果与期望输出结果相符。

1. 测试实例2

程序输入

s：ababvab

t1：ab

t2：aa

程序输出

结论

程序输出结果与期望输出结果相符。

1. 测试实例3

程序输入

s：abcab

t1：ab

t2：c

程序输出

结论

程序输出结果与期望输出结果相符。

源代码：

#include <iostream>
using namespace std;
// 定义串,最大容量255,第一个位置不放元素
typedef struct {
    char s[256];
    int length;
}SString;
// 从键盘录入字符,完成三个串的初始化
void get_str(SString& s, SString& t1, SString& t2) {
    // 定义字符变量,读取缓冲区字符
    char ch;
    // 记录串长度
    int count = 0;
    cout << "请输入主串s:" << endl;
    // 一次读取一个字符
    ch = getchar();
    // 当没读到换行符和长度小于255时进入循环
    while (ch != '\n' && count < 255)
    {
        ++count;
        s.s[count] = ch;
        ch = getchar();
    }
    // 一个串读取完毕,将长度赋值
    s.length = count;
    // t1和t2子串的读取和主串s的读取一致
    count = 0;
    cout << "请输入子串t1:" << endl;
    ch = getchar();
    while (ch != '\n' && count < 255)
    {
        ++count;
        t1.s[count] = ch;
        ch = getchar();
    }
    t1.length = count;
    count = 0;
    cout << "请输入子串t2:" << endl;
    ch = getchar();
    while (ch != '\n' && count < 255)
    {
        ++count;
        t2.s[count] = ch;
        ch = getchar();
    }
    t2.length = count;
}
// kmp算法
int kmp(SString s, SString t, int pos, int next[]) {
    // 利用模式串t的next函数求t在主串s中第pos个字符之后的位置
    // 其中t非空,1<=pos<=s.length
    int i = pos, j = 1;
    // 两个串均未比较到串尾
    while (i <= s.length && j <= t.length)
    {
        // 继续比较后继字符
        if (s.s[i] == t.s[j] || j == 0) {
            ++i;
            ++j;
        }
        else {
            // 模式串向右移动
            j = next[j];
        }
    }
    // 匹配成功
    if (j > t.length) {
        return i - t.length;
    }
    else {
        // 匹配失败
        return 0;
    }
}
// 求next值并存入next数组
void Next(SString t, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i <= t.length)
    {
        if (j == 0 || t.s[i] == t.s[j]) {
            ++i;
            ++j;
            next[i] = j;
        }
        else {
            j = next[j];
        }
    }
}
// 替换时主串其他字符移动情况
void move(SString& s, int pos, int dis) {
    // 如果t1和t2长度一样,其他字符不用移动
    if (!dis) {
        return;
    }
    // t2串比t1串长,匹配成功的t1串后的字符向后移
    if (dis > 0) {
        int i;
        if (s.length + dis > 255) {
            i = 255 - dis;
        }
        else {
            i = s.length;
        }
        while (i >= pos)
        {
            s.s[i + dis] = s.s[i];
            --i;
        }
        s.length += dis;
    }
    else {
        // t1串比t2串长,匹配成功的t1串后的字符向前移
        dis = -dis;
        while (pos <= s.length)
        {
            s.s[pos - dis] = s.s[pos];
            ++pos;
        }
        s.length -= dis;
    }
}
// 输出串所有字符
void print(SString& s) {
    for (int i = 1; i <= s.length; ++i) {
        cout << s.s[i];
    }
}
int main(void) {
    // 定义串
    SString s, t1, t2;
    // 定义 start:匹配开始位置   begin:替换开始位置   length_dif:t1和t2长度之差  count:替换次数
    int start = 1, begin, length_dif, count = 0;
    // 定义next数组
    int next[256];
    get_str(s, t1, t2);
    length_dif = t2.length - t1.length;
    Next(t1, next);
    while (1)
    {
        // 得到替换开始位置
        begin = kmp(s, t1, start, next);
        // 如果未找到退出循环
        if (!begin) {
            break;
        }
        ++count;
        // 下一次的匹配开始位置
        start = begin + t2.length;
        // 移动后续的字符
        move(s, begin + t1.length, length_dif);
        // t2串替换t1串
        for (int i = 1; i <= t2.length; ++i, ++begin) {
            s.s[begin] = t2.s[i];
        }
    }
    // 输出结果
    cout << "替换后的s: ";
    print(s);
    cout << "   替换次数: " << count << endl;
    return 0;
}