题目要求

建立一个字符文件。从键盘输入字符文件名以及子串，程序首先求取子串的 nextval 数组，然后用改进 KMP 算法在文件中查找子串，最后在屏幕上显示输出子串在文件中的匹配次数。若文件中无子串，输出匹配次数为 0。

涉及知识点

串、改进 KMP 算法、字符串查找、模式匹配。

数据结构设计

用字符数组，定义两个字符串：主串 s 和子串 t。主串通过文件输入保存，子串通过控制台输入。

算法设计简要描述

串的模式匹配算法，与子串定位的算法概念相同，即在主串 s 中查找子串 t(称为模式)第一次出现的起始位置。
通过改进 KMP 算法，可以使得文件一次扫描的条件下，不遗漏地找到所有子串与主串成功匹配的位置下标，并记录成功匹配的总次数。

程序代码

#include<iostream>
#include<fstream>
using namespace std;
void read(char *filename,char *s)        // 读取数据,filename 代入不同的文件名,s 为主串
{
    char c;
    int i = 0;
    ifstream infile(filename);
    if (!infile)                           // 打开文件失败输出提示信息
    {
        cout << "file open error!" << endl;
        exit(0);
    }
    while (1)                              // 读入字符，保存在主串中
    {
        infile >> c;
        if (infile.eof())
        break;
        s[i] = c;
        i++;
    }
    s[i] = '\0';
    cout << "主串为:";                    // 输出主串
    for (i = 0; i < strlen(s); i++)
        cout << s[i];
    cout << endl;
    infile.close();}
void get_next(char *t, int next[])         // 求 next 数组，t 为子串
{
    int j, k;
    next[0] = k = -1;
    j = 1;
    while (j <= strlen(t) + 1)             // 为避免文件回溯，求到 next[m]值
    {if (k == -1 || t[j - 1] == t[k])
            next[j++] = ++k;
        else
            k = next[k];
    }
}
void get_nextval(char *t, int nextval[], int next[])    // 求 nextval 数组，t 为子串
{
    int j, k;
    nextval[0] = k = -1;
    j = 1;
    while (t[j])
    {if (k == -1 || t[j - 1] == t[k])
            if (t[++k] == t[j])
                nextval[j++] = nextval[k];
            else
                nextval[j++] = k;
        else
            k = nextval[k];
    }
    nextval[strlen(t)] = next[strlen(t)];   //nextval[m]即为 next[m]的值
}
int index_kmp(char *s, char *t, int nextval[], int &num)    /*KMP 算法: 子串的模式匹配,s 为主                                             
                                                            串,t 为子串,num 记录匹配的次数 */
{
    int i, j, flag = 1, location;           /*flag 为标量，第一次匹配时 flag 为 1，否则 flag 为                                         
                                            0，location 记录第一次匹配的位置下标 */
    i = j = 0;  
    while (s[i] && (j == -1 || t[j]))
    {if (j == -1 || s[i] == t[j])
        {
            i++;
            j++;
        }
        else
            j = nextval[j];
        if (!t[j])
        {if (flag == 1)                  // 第一次匹配，location 记录匹配的位置下标
            {
                location = i - j;
                flag = 0;
                cout << "子串出现的位置分别为:";
            }
            cout << i - j << " ";         //i - j 为每次匹配的位置下标
            j = nextval[strlen(t)];         // 匹配成功后，j 就从 nextval[m]开始继续查找
            num++;                          //num 记录匹配的次数
        }
    }
    if(flag == 1)                           //flag 恒为 1 表示没有一次成功的匹配
    {
        location = -1;                      //location 为 - 1 表示匹配失败
        cout << "匹配失败!";
    }
    cout << endl;
    return location;                        // 返回第一次匹配的位置下标
}
 
int main()
{int nextval[20], next[20], i, location, num = 0;    /*location 记录第一次匹配的位置，num 记录匹配的次数 */
    char t[20], s[20], filename[20];        // t 为子串，s 为主串，filename 为文件的名称
    cout << "请输入文件的名称:";
    cin >> filename;
    read(filename, s);                      // 从文件中读取主串
    cout << "请输入子串:";
    cin >> t;                               // 输入子串
    while (strlen(t) > strlen(s))           // 输入错误，重新输入
    {cout << "输入错误(子串长度大于主串长度), 请重新输入:";
        cin >> t;
    }
    get_next(t, next);
    cout << "next 数组为:";
    for (i = 0; i < strlen(t) + 1; i++)     //next 数组多一个元素，用来记录子串回溯的位置
        cout << next[i] << " ";
    get_nextval(t, nextval, next);
    cout << endl << "nextval 数组为:";
    for (i = 0; i < strlen(t) + 1; i++)     //nextval[m]即为 next[m]的值，记录子串回溯的位置
        cout << nextval[i] << " ";
    cout << endl;
    location = index_kmp(s, t, nextval, num);
    if (location != -1)                     //location 不为 1 表示匹配成功
    {
        cout << "子串在主串中第一次出现的起始位置为:" << location << endl;
        cout << "子串在主串中匹配的次数为:" << num << endl;
    }
    return 0;
}

示例

（1）程序输入 ：

主串 s: bacbababadababacambabacaddababacasdsd
子串 t: ababaca

程序输出 ：
第一次出现的起始位置：10
匹配次数：2

（2）程序输入 ：

主串 s: aaaaaaaaaaaaa
子串 t: aaa

程序输出 ：
第一次出现的起始位置：0
匹配次数：11

（3）程序输入 ：

主串 s: abcbabcbabcbabcba
子串 t: abcba

程序输出 ：
第一次出现的起始位置：0
匹配次数：4

（4）程序输入 ：

主串 s: abcbabcbabcbabcba
子串 t: abcde
程序输出 ：
匹配失败！