Question

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

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 *next)
{
int i=0,j=-1;
next[i]=-1;
while(i<T.length)
{
if(j==-1||T.s[i]==T.s[j])
//当ti=tj时，i和j分别加1，同时计算next[j]，再继续比较；
//当j==-1时，则使si+1与t0比较，同上。
{
i++;
j++;
next[i]=j;//给数组next的元素赋值
}
else j=next[j];//不匹配，则给出新j值
}
}
//============================================================
template <class T1>
int string<T1>::index(const string<T1> &T,int pos)
{
int *next=new int[T.length];
getnext(T,next);
int i=pos-1,j=0;
while ( i<length && j<T.length )
{
if (j==-1|| s[i]==T.s[j] ) {++i;++j;}
//不失配则继续比较后续字符
else {j=next[j];}
//S的i指针不回溯，从T的k位置开始匹配
}
if(j>=T.length)
return i-T.length+1; //子串结束，说明匹配成功位置
else return -1;
}

如上，对于1、2，分别写出完整的可直接运行的main函数，不一定要用模板（最好不用），这对高手来说是小菜一碟吧，复制粘贴，写个主函数，加点东西，再修改修改就好了，万分感谢，测试成功再补100分！！！
在线等，很急，测试成功，立即给分，加分！！！！！
-------------------------------------------------------
已经不需要了，nnd，白白浪费了200分……

Answer 1

#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 || s[i] == ss[j]) {
i++;
j++;
next[i]=j;
} else
j = next[j];
}
}

int index2(const string ss, int pos)
{
int *next = new int[ss.length()];
getnext(ss, next);

int i = pos, j = 0;
while (i < s.length() && j < ss.length()) {
if (j==0 || s[i]==ss[j] ) {
++i;
++j;
} else {
j = next[j];
}
}

if (j >= ss.length())
return i-ss.length()+1;
else
return -1;
}

int main()
{
string ss = "abc";
printf("index1: %d, index2: %d\n", index1(ss, 0), index2(ss, 0));

return 0;
}

Answer 2

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

Answer 3

恩,百度提问太差了 我都丢了几次高分都没有成功!
我估计丢了500分了不是乱答就是没通过,分又没有