シリアルのパターンマッチングの問題

1477 ワード

3つの方法があります
1、直接マッチング2、首尾マッチング3、KMPアルゴリズム
(1)最初の2つのアルゴリズムの時間複雑度はO(M*N)である.後者はO(m+n)
(2)アルゴリズム1は実際に時間近似O(m+n)を実行し,KMPアルゴリズムはモード列と主列の間に多くの部分的な整合がある場合にのみ効率的である.
しかし,KMPアルゴリズムの利点は,主列ポインタが遡及せず,周辺機器から入力された膨大なデータファイルを処理するのに有効であり,読み込みながらマッチングでき,後で読み直す必要がないことである.
1、直接整合法

int index(SString S, SString T, int pos)
{
    i=pos; j=1;
    while(i<=S[0]||j<=T[0])
    {
        if(S[i]==T[j])    {i++;    j++;}
        else 
            {i=i-j+2;  j=1;}
    }
    if(j>T[0])    return i-j+1;
    else
        return 0;
}
// :  T[0]     T   ，     T[1]

2、首尾照合

int index(SString S, SString T, int pos)
{
    sLength=S[0];    tLength=T[0];   
    i=pos; 
    while(i<=sLength-tLength+1)
    {
        if(S[i]!=S[1])    ++i;
        else if(S[i+tLength-1]!=T[tLength])    ++i; 
        else
        {
             k=1;j=2;    
             while(j

3、KMPアルゴリズム

int index(SString S, SString T, int pos)
{
    i=pos; j=1;
    while(i<=S[0]||j<=T[0])
    {
        if(S[i]==T[j])    {i++;    j++;}
        else 
           j = next[j];    
    }
    if(j>T[0])    return i-j+1;
    else
        return 0;
}

void get_next(SString T, int next[])  
{
    i=1; next[1]=0; j=0;
    while(i

転載先:https://www.cnblogs.com/CanWork/archive/2012/11/27/2791417.html

【アルゴリズム】アルゴリズム試験問題5:牛の数列:最長連続サブシーケンス

Kmpアルゴリズムのまとめ