【数据结构】——基于改进KMP算法的文件字符串查找

题目要求

建立一个字符文件。从键盘输入字符文件名以及子串，程序首先求取子串的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
程序输出：
匹配失败！