Kmp字符匹配算法优化C++实现

C++实现Kmp字符匹配算法的优化版

 

头文件:KmpAlgorithm.h

#ifndef KMPALGORITHM_H
#define KMPALGORITHM_H
#include <string>
#include <iostream>
class KmpAlgorithm{
std::string s; //主串
std::string t; //子串
static const int MaxSize = 255;
int next[MaxSize];
void Get_Next(); //T串的模式匹配函数
public:
KmpAlgorithm(){
std::memset(next,0,sizeof(int) * 255);
printf("请输入要匹配的字符串的主串:\n");
std::cin >> s;
printf("请输入要匹配的字符串的子串:\n");
std::cin >> t;
}
int Index_Kmp(int pos);  //字符匹配函数
};
#endif //KMPALGORITHM_H

实现文件:KmpAlgorithm.cpp

#include "KmpAlgorithm.h"
void KmpAlgorithm::Get_Next()
{
int i,j;
i = 0;
j = -1;
next[0] = -1;
while(i < t.size()-1)
{
if(j == -1 || t[j] == t[i]) //如果相等则继续
{//next[0] == -1 j的值有可能回溯为-1数组越界
++i;
++j;
if(t[j] != t[i]) //如果下面两个字符不相等则把j的值赋给next在i位置的值
next[i] = j;
else
next[i] = next[j]; //相等则把next在j位置的值赋给next在i位置的值
}
else
j = next[j];
}
}
int KmpAlgorithm::Index_Kmp(int pos) //字符匹配函数
{
int  i = pos - 1; //数组从下标0开始
int j = 0;
Get_Next(); 
while(i < s.size() && j < t.size()) 
{
if(j == -1 || s[i] == t[j]) //如果相等继续
{//如果j的值回溯到-1 next[0] == -1 则继续否则数组越界
++i;
++j;
}
else
{
j = next[j]; //不相等则回溯
}
}
if(j >= t.size()) //匹配成功返回在主串中的位置
return i - t.size() + 1;
else
return -1; //失败返回-1
}

测试文件:main.cpp

#include "KmpAlgorithm.h"
#include <iostream>
using namespace std;
int main()
{
int pos = 0;
KmpAlgorithm km;
printf("请输入在主串的第几个字符开始匹配:\n");
scanf("%d",&pos);
int position = km.Index_Kmp(pos);
if(position == -1)
printf("在主串中未找到与子串匹配的字符:\n");
else
printf("在主串的第%d个位置匹配成功\n",position);
return 0;
}