字符串匹配算法及另外的操作

字符串匹配+統(tǒng)計比較次數(shù)

/***字符串匹配算法***/
#include<cstring>
#include<iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255           //用戶可在255以內(nèi)定義最長串長
typedef struct {        //0號單元存放串的長度
 char ch[MAXSTRLEN+1];
 int length;
  }SString;
Status StrAssign(SString &T, char *chars) { //生成一個其值等于chars的串T
    int i;
    if (strlen(chars) > MAXSTRLEN)
        return ERROR;
    else {
        T.length = strlen(chars);
        for (i = 1; i <= T.length; i++)
            T.ch[i] = *(chars + i - 1);
        return OK;
    }
}

//填寫4.1　BF算法 并增加計算比較次數(shù) 
int Index_BF(SString S, SString T, int pos)
{
    //返回模式T在主串S中第pos個字符之后第s一次出現(xiàn)的位置。若不存在，則返回值為0
    //其中，T非空，1≤pos≤StrLength(S)
    int i=pos; int j=1;
    int count1=0;
    while(i<=S.length&&j<=T.length){
        count1++;
//      cout<<"比較次數(shù)為:"<<count1<<endl;
        if(S.ch[i]==T.ch[j]){
            ++i;++j;
        }else{
            i=i-j+2;j=1;
        }
        
    }
    cout<<"比較次數(shù)為:"<<count1<<endl;
    if(j>T.length)
            return i-T.length;
        else return 0;
    

}//Index
//算法4.3　計算next函數(shù)值
void get_next(SString T, int next[])
{ //求模式串T的next函數(shù)值并存入數(shù)組next
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length)
        if (j == 0 || T.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
}//get_next

//算法4.2　KMP算法,增加計算比較次數(shù)
int Index_KMP(SString S, SString T, int pos, int next[])
{   // 利用模式串T的next函數(shù)求T在主串S中第pos個字符之后的位置的KMP算法
    //其中，T非空，1≤pos≤StrLength(S)
    int i = pos, j = 1;
    int count2=0;
    while (i <= S.length && j <= T.length)
    {   
        count2++;
        //cout<<"比較次數(shù)為:"<<count2<<endl;
    if (j == 0 || S.ch[i] == T.ch[j]) // 繼續(xù)比較后繼字
        {
            ++i;
            ++j;
        }
        else
            j = next[j]; }// 模式串向右移動
    cout<<"比較次數(shù)為:"<<count2<<endl;
    if (j > T.length) // 匹配成功
        return i - T.length;
    else
        return 0;
     
}//Index_KMP
int main()
{
    SString S;
    StrAssign(S,"bbabababababba") ;
    SString T;
    StrAssign(T,"babb") ;
    
    cout<<"調(diào)用BF算法:"<<endl; 
    cout<<"主串和子串在第"<<Index_BF(S,T,1)<<"個字符處首次匹配\n";
    int *p = new int[T.length+1]; // 生成T的next數(shù)組
    get_next(T,p);
    cout<<"調(diào)用KMP算法:"<<endl;
    cout<<"主串和子串在第"<<Index_KMP(S,T,1,p)<<"個字符處首次匹配\n";
    return 0;
}

統(tǒng)計匹配字符串+統(tǒng)計子串出現(xiàn)次數(shù)

/***字符串匹配算法***/
#include<cstring>
#include<iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255           //用戶可在255以內(nèi)定義最長串長
typedef struct {        //0號單元存放串的長度
 char ch[MAXSTRLEN+1];
 int length;
  }SString;
Status StrAssign(SString &T, char *chars) { //生成一個其值等于chars的串T
    int i;
    if (strlen(chars) > MAXSTRLEN)
        return ERROR;
    else {
        T.length = strlen(chars);
        for (i = 1; i <= T.length; i++)
            T.ch[i] = *(chars + i - 1);
        return OK;
    }
}

//填寫4.1　BF算法 并增加計算比較次數(shù) 
int Count_BF(SString S, SString T, int pos)
{
    //返回模式T在主串S中第pos個字符之后第s一次出現(xiàn)的位置。若不存在，則返回值為0
    //其中，T非空，1≤pos≤StrLength(S)
    int count=0;
    int i=pos;
    int j=1;
    for(i=pos;i<=S.length;){
        //cout<<i;
    while(i<=S.length&&j<=T.length){

        if(S.ch[i]==T.ch[j]){
            ++i;++j;
        }else{
            i=i-j+2;j=1;
        }
        
    }
    if(j>T.length){
        pos = i-T.length;
        i=i-j+2;
        j=1;
//      cout<<pos<<"&"<<i<<endl;
        count++;
        continue;
    }
}
    return count;
    

}//Index
//算法4.3　計算next函數(shù)值
void get_next(SString T, int next[])
{ //求模式串T的next函數(shù)值并存入數(shù)組next
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length)
        if (j == 0 || T.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
}//get_next

//算法4.2　KMP算法,增加計算比較次數(shù)
int Index_KMP(SString S, SString T, int pos, int next[])
{   // 利用模式串T的next函數(shù)求T在主串S中第pos個字符之后的位置的KMP算法
    //其中，T非空，1≤pos≤StrLength(S)
    int i = pos, j = 1,count=0;
    for(i=pos;i<=S.length;){
        while (i <= S.length && j <= T.length)
    {   
    if (j == 0 || S.ch[i] == T.ch[j]) // 繼續(xù)比較后繼字
        {
            ++i;
            ++j;
        }
        else
            j = next[j]; }// 模式串向右移動

    if (j > T.length) // 匹配成功
        pos = i - T.length;
        i=i+1;
        j=1;
        count++;
    }

    return count;   
        
     
}//Index_KMP
int main()
{
    SString S;
    StrAssign(S,"bbababbbababababbababb");
            //bba babb bababa babb a babb 3次 
    SString T;
    StrAssign(T,"babb") ;
    
    cout<<"調(diào)用BF算法:"<<endl; 
    cout<<"子串在主串中出現(xiàn)"<<Count_BF(S,T,1)<<"次\n";
    int *p = new int[T.length+1]; // 生成T的next數(shù)組
    get_next(T,p);
    cout<<"調(diào)用KMP算法:"<<endl;
    cout<<"子串在主串中出現(xiàn)"<<Index_KMP(S,T,1,p)<<"次\n";
    return 0;
}