数据结构（c++）字符串 模式匹配算法问题，对高手来说只要写一点点

来源：百度知道 编辑：UC知道 时间：2024/06/23 02:14:53
1、在串堆存储表示的基础上串匹配的BF算法实现
前置条件：串已存在
输入：输入子串对象ss，输入从主串第i位开始查找子串
动作：寻找子串在在主串第i位后子串第一次出现的位置。
输出：返回匹配子串的位置，否则不匹配则返回-1值。
后置条件：无

核心部分参考：
template <class T1>
int string<T1>::index(const string<T1> &T,int pos)
{//在S串中从pos开始查找一个与串T相同的子串
if (pos<1||pos>length) throw "pos不合法！";
int i=pos,j=1;
while (i<=length &&j<=T.length)
{
if (s[i]==T.s[j])
{
i++;
j++;
}
else
{
i=i-j+2;
j=1;//回溯
}
}
if (j>T.length) return (i-j+1);
else return -1;
}

2、在串堆存储表示的基础上串匹配的KMP算法实现
前置条件：串已存在
输入：输入子串对象ss，输入从主串第i位开始查找子串
动作：寻找子串在在主串第i位后子串第一次出现的位置。
输出：返回匹配子串的位置，否则不匹配则返回-1值。
后置条件：无

核心部分参考：
template <class T1>
void string<T1>::getnext(const string<T1> &T,int *

唉，还是去CSDN问吧，百度知道太水了，都是些弱智题。以后不来了。。

#include <string>
using namespace std;

string s = "zabcdefg";

int index1(const string ss, int pos)
{
if (pos<0 || pos>s.length())
printf("pos²»ºÏ·¨£¡");
int i = pos, j = 0;

while (i < s.length() && j < ss.length()) {
if (s[i]==ss[j]) {
i++;
j++;
} else {
i=i-j+1;
j=0;
}
}

if (j>=ss.length())
return (i-j+1);
else
return -1;
}
void getnext(const string ss, int *next)
{
int i = 0, j = -1;
next[i] = -1;
while (i < ss.length()) {
if (j == -1 ||