C奇怪的字符串问题
温习KMP模式匹配时遇到的问题
当将main中按char a[]= "abababb ";int next[7];顺序写,执行后,a[0]到a[3]都变为0,其它正常;当按int next[7];char a[]= "abababb ";顺序写，执行后,结果正确当最后弹出报错;当将int next[7];写到main外作为全局变量,执行成功，结果正确。请问是为什么会这样？
最近都在做web程序，最基础的都有点忘了，请各位指教（在VC6中编写)
void Get_next(char *p,int next[])
{
int i,j,slen;
slen=strlen(p);i=0;
next[0]=-1;j=-1;
while (i <slen)
{
if (j==-1||p[i]==p[j])
{
++i;++j;next[i]=j;
}
else
j = next[j];
}
}
int main(int argc, char* argv[])
{
char a[]= "abababb ";
int next[7];
int i;
Get_next(a,next);
for (i=0;i <6;i++)
{
cout < < "a[ " < <i < < "]= " < <a[i] < <endl;
cout < < "next[ " < <i < < "]= " < <next[i] < <endl;
}
return 0;
}
[解决办法]
讨论一般情况。
假设 主串：s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 ：p: ‘p(1) p(2) p(3)…..p(m)’
把课本上的这一段看完后，继续
现在我们假设 主串第i个字符与模式串的第j(j <=m)个字符‘失配’后，主串第i个字符与模式串的第k(k <j)个字符继续比较
此时，s(i)≠p(j), 有
主串： S(1)…… s(i-j+1)…… s(i-1) s(i) ………….
|| (相配) || ≠(失配)
匹配串： P(1) ……. p(j-1) p(j)
由此，我们得到关系式
‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’
由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在 k’> k 满足下列关系式：(k <j),
‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’
即：
主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….
|| (相配) || || ?(有待比较)
匹配串： P(1) p(2) …… p(k-1) p(k)
现在我们把前面总结的关系综合一下
有：
S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……
|| (相配) || || || ≠(失配)
P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)
|| (相配) || || ?(有待比较)
P(1) p(2) ……. p(k-1) p(k)
由上，我们得到关系：
‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(j-k+1)s(j-k+2)……s(j-1)’
接下来看“反之，若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。
K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少.
附：
KMP算法查找串S中含串P的个数count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
inline void NEXT(const string& T,vector <int> & next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;i <T.size();i++ ){
int j=next[i-1];
while(T[i]!=T[j+1]&& j> =0 )
j=next[j] ; //递推计算
if(T[i]==T[j+1])next[i]=j+1;
else next[i]=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空，
vector <int> next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index <S.size();++index){
int pos=0;
string::size_type iter=index;
while(pos <T.size() && iter <S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()&&(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S= "abaabcacabaabcacabaabcacabaabcacabaabcac ";
string T= "ab ";
string::size_type count=COUNT_KMP(S,T);
cout < <count < <endl;
system( "PAUSE ");
return 0;
}
[解决办法]
可能是你这数组定义小了一点
int next[7];
而你求next的函数连串后的 '\0 '位置也要计算
没有看代码,但你这是越界覆盖的典型症状.你把next数组定大一点看.
[解决办法]
计算方法有误，
楼主再回顾看看 KMP 算法先 ～
