14

長いタイトルでごめんなさい:)

この問題では、長さの文字列と長さ のS文字列があります。が時間計算量 O(n+m)の文字列のサブシーケンスであるかどうかを確認できます。それは本当に簡単です。nTmST

私が興味を持っているのは、最大でもK連続する文字を削除できるとしたら? たとえば、 の場合K = 2、 からは作成できますが、"ab"からは作成でき"accb"ません"abcccb"。それが可能かどうかを非常に迅速に確認したい。

私は明らかなことしか見つけられませんでした： stringと stringO(nm)のすべての接尾辞のペアが可能かどうかを確認してください。貪欲なアルゴリズムが可能かもしれないと思ったのですが、もし、ケースandは反例です。STK = 2S = "abc"T = "ababbc"

この問題を解決するための迅速な解決策はありますか?

4

7 に答える 7

0

再帰的なアプローチを考えてみましょう: int f(int i, int j)T[j...m] に一致する S[i...n] の最初の可能な最小ギャップを示します。そのような一致が存在しない場合fに返します。-1の実装は次のfとおりです。

int f(int i, int j){
    if(j == m){
        if(i == n)
            return 0;
        else
            return -1;
    }
    if(i == n){
        return m - j;
    }

    if(S[i] == T[j]){
        int tmp = f(i + 1, j + 1);
        if(tmp >= 0 && tmp <= k)
            return 0;
    }
    return f(i, j + 1) + 1;
}

この再帰的アプローチを動的計画法のアプローチに変換すると、 の時間計算量を持つことができますO(nm)。

于 2013-11-12T04:45:49.970 に答える
0

これは、通常* O(N) で実行され、O(m) スペースを取る実装です。ここで、m は長さ (S) です。

これは、測量士の鎖のアイデアを使用しています
。長さ k の鎖でつながれた一連の極を想像してください。弦の最初に最初のポールを固定します。一致する文字が見つかるまで、次の極を進めます。そのポールを置きます。たるみがある場合は、次の文字に進みます。それ以外の場合は、前の極が前方にドラッグされているため、戻って次に近い一致に移動する必要があります。最後に到達するか、たるみがなくなるまで繰り返します。

typedef struct chain_t{
    int slack;
    int pole;
 } chainlink;


int subsequence_k_impl(char* t, char* s, int k, chainlink* link, int len)
{
  char* match=s;
  int extra = k; //total slack in the chain

  //for all chars to match, including final null
  while (match<=s+len){
     //advance until we find spot for this post or run out of chain
     while (t[link->pole] && t[link->pole]!=*match ){
        link->pole++; link->slack--;
        if (--extra<0) return 0; //no more slack, can't do it.
     }
     //if we ran out of ground, it's no good
     if (t[link->pole] != *match) return 0;

    //if this link has slack, go to next pole
     if (link->slack>=0) { 
        link++; match++;
        //if next pole was already placed,
        while (link[-1].pole < link->pole) {
          //recalc slack and advance again
          extra += link->slack = k-(link->pole-link[-1].pole-1);
          link++; match++;
        }
        //if not done
        if (match<=s+len){
          //currrent pole is out of order (or unplaced), move it next to prev one
          link->pole = link[-1].pole+1; 
          extra+= link->slack = k;         
        }
     }
    //else drag the previous pole forward to the limit of the chain.
     else if (match>=s) {
        int drag = (link->pole - link[-1].pole -1)- k;
        link--;match--;
        link->pole+=drag;
        link->slack-=drag;
     }
  }
  //all poles planted.  good match
  return 1;
}

int subsequence_k(char* t, char* s, int k)
{
  int l = strlen(s);
  if (strlen(t)>(l+1)*(k+1)) 
     return -1;   //easy exit
  else {
     chainlink* chain = calloc(sizeof(chainlink),l+2);
     chain[0].pole=-1; //first pole is anchored before the string
     chain[0].slack=0;
     chain[1].pole=0; //start searching at first char
     chain[1].slack=k;
     l = subsequence_k_impl(t,s,k,chain+1,l);
     l=l?chain[1].pole:-1; //pos of first match or -1;
     free(chain);
  }
  return l;
}

※big-Oはよくわかりません。最初はO(km+N)のようなものだと思っていました。テストでは、一致が良好な場合は平均 2N 未満であり、一致しなかった場合は N 未満です。
...しかし.. 奇妙な縮退のケースがあります。サイズ のアルファベットから選択されたランダムな文字列のA場合、k = 2A+1. この場合でも O(Nm) よりも優れており、k を少し増減すると O(N) に戻ります。 Gist誰かが興味を持っている場合は、ここを参照してください。

于 2013-11-21T13:45:23.017 に答える