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分……