[收集]]关于KMP算法!

栈是整个副本拷贝了，不过引用是c＋＋的概念．．还好．．我还以为概念错了呢．．呵呵，觉得奇怪，刚才没太在意．．翅膀兄弟越来越细心了．．．楼上兄弟下次我们也要小心点．．不要被翅膀抓住．．呵呵

[[it] 本帖最后由 sunkaidong 于 2008-5-28 15:51 编辑 [/it]]
----------------解决方案--------------------------------------------------------
那啥……KMP函数仍然是复制传参的……Orz，而且是复制两个……
其实啊，如果要通用，直接处理0结尾的字符串就可以了，传个指针进来……
----------------解决方案--------------------------------------------------------
int Index_KMP(stack_ch S,stack_ch T,int pos,int *next,int m)   哦这里问题。。。还是引用好了

[[it] 本帖最后由 sunkaidong 于 2008-5-29 15:19 编辑 [/it]]
----------------解决方案--------------------------------------------------------
c-,- 俺也贴个出来 ,写了很久了..
#include <iostream>
#include <cstring>
#define SIZE 13
using namespace std;


int Index_Bf(char *S,char *T){        //普通的匹配
    int i=0,j=0;
    while(S[i]!='\0'&&T[j]!='\0'){
        if(S[i]==T[j]){
            j++;
            i++;
        }
        
        else{
              i=i-j+1;j=0;
            }
        }
        if(T[j]=='\0')
           return i-j;
           else
           return false;
}
        
void Get_next(char *T,int *next){    //next求法
    int j=-1;
    int i=0;
    next[0]=-1;
    while(i<strlen(T)) {
        if(j==-1 || T[i]==T[j])
        {
            i++;
            j++;
            next[i]=j;
            }
            else
            j=next[j];
        }
    for(j=0;j<i;j++)
    cout<<next[j]<<" ";
   
}


void Get_nextval(char *T,int *next){     //改进后的next求法
    int j=-1;
    int i=0;
    next[0]=-1;
    while(i<strlen(T)) {
        if(j==-1 || T[i]==T[j]){
            i++;
            j++;
            if(T[i]!=T[j])next[i]=j;
            else next[i]=next[j];
        }
        else j=next[j];
    }
    for(j=0;j<i;j++)
    cout<<next[j]<<" ";
   
}


int Index_KMP(char *S,char *T,int *next){        //KMP算法
    int i=0,j=0;
    while(S[i]!='\0'&&T[j]!='\0'){
        if(S[i]==T[j]){
            j++;
            i++;
        }
        
        else{
              j=next[j];
            }
        }
        if(T[j]=='\0')
           return i-strlen(T);
           else
           return false;
}   
   
int main(){
    char S[]="bcaaaabc";
    char T[]="aaaab";
    int next[SIZE];
   //Get_next(T,next);
    Get_nextval(T,next);
    cout<<"T is found in "<<Index_KMP(S,T,next)<<";if return 0 ,fail."<<endl;
   
    system("pause");
    return 0;
}
----------------解决方案--------------------------------------------------------