2

2 つの文字列 S と T が与えられます。ここで、T はパターン文字列です。パターン文字列のスクランブル形式が文字列 S に SubString として存在するかどうかを調べ、存在する場合は開始インデックスを返します。

例：

文字列 S: abcdef 文字列 T: efd

文字列 S には、検索文字列 T: "efd" の組み合わせである "def" があります。

実行時間が O(m*n) のソリューションを見つけました。私は、HashMaps (文字列 T 用に維持された静的なものと、T の現在の部分文字列をチェックするために使用される以前の HashMap の動的コピー) を使用していた線形時間ソリューションに取り組んでいます。失敗した次の文字からチェックを開始します。しかし、これは最悪の場合 O(m*n) で実行されます。O(m+n) 時間で動作させるためのポインタをいくつか取得したいと思います。どんな助けでも大歓迎です。

4

5 に答える 5

3

まず、文字列のS長さ(m)とパターンのT長さの境界を知りたい(n)です。

一般的な考え方は 1 つありますが、それに基づくソリューションの複雑さはパターンの長さに依存します。O(m)複雑さはO(m*n^2)、短いパターンとlength<=100長いO(n)パターンの場合で異なります。

算術の基本定理は、すべての整数を素数の積として一意に表すことができると述べています。

アイデア - あなたのアルファベットは英字だと思います。したがって、アルファベットのサイズは 26 です。最初の文字を最初のプライムに、2 番目の文字を 2 番目のプライムに、というように置き換えましょう。次の置換を意味します:
a->2
b->3
c->5
d->7
e->11 など。

ある文字列の文字に対応する素数の積を としましょうprime product(string)。たとえば、はprimeProduct(z)そのまま26 番目の素数になります。101101primeProduct(abc)2*3*5=30primeProduct(cba)5*3*2=30

なぜ素数を選ぶのか? a ->2; を置き換えると、b ->3、c->4、例 4 を解読することはできません - それは "c" なのか "aa" なのか。

短いパターンの場合の解決策: 文字列 S の場合、すべてのプレフィックスの線形時間素数積を計算する必要があります。つまり、 、、のような配列 A を作成する必要があります。実装例:A[0] = primeProduct(S[0])A[1] = primeProduct(S[0]S[1])A[N] = primeProduct(S)

A[0] = getPrime(S[0]);
for(int i=1;i<S.length;i++)
    A[i]=A[i-1]*getPrime(S[i]);

パターン T を検索します。primeProduct(T) を計算します。パターンと同じ長さを持つ Sのすべてについて'windows'、primeProduct と primeProduct(pattern) を比較します。currentWindow がパターンと等しい場合、または currentWindow がパターンのスクランブル形式 (アナグラム) である場合、primeProducts は同じになります。

重要な注意点！S の任意の部分文字列に対してprimeProduct を高速に計算するために、配列 A を用意しました。= = ;primeProduct of(S[i],S[i+1],...S[j])getPrime(S[i])*...*getPrime(S[j])A[j]/A[i-1]

'zzzzzzzzz'複雑さ: パターンの長さが<=9 の場合101^9<=MAX_LONG_INT、すべての計算は標準の long 型に適合し、複雑さは O(N)+O(M) です。ここで、N はパターンの primeProduct を計算するためのもので、M は のすべてのウィンドウで反復処理を行いますS。length<=100 の場合、mul/div の長い数値の複雑さを追加する必要があるため、複雑さが になりO(m*n^2)ます。長さ 101^長さは O(N) mul/div のような長い数値はO(N^2)

長さが 1000 以上の長いパターンの場合は、ハッシュ マップ (素数、次数) を格納することをお勧めします。プレフィックスの配列はハッシュ マップの配列になり、A[j]/A[i-1]トリックは differenceBetween(A[j] と A[i-1] ハッシュマップのキー セット) になります。

于 2013-07-31T04:26:17.740 に答える
1

この JavaScript の例は線形時間でしょうか?

<script>

function matchT(t,s){
  var tMap = [], answer = []

  //map the character count in t
  for (var i=0; i<t.length; i++){
    var chr = t.charCodeAt(i)

    if (tMap[chr]) tMap[chr]++
    else tMap[chr] = 1
  }

  //traverse string
  for (var i=0; i<s.length; i++){
    if (tMap[s.charCodeAt(i)]){
      var start = i, j = i + 1, tmp = []

      tmp[s.charCodeAt(i)] = 1

      while (tMap[s.charCodeAt(j)]){
        var chr = s.charCodeAt(j++)

        if (tmp[chr]){
          if (tMap[chr] > tmp[chr]) tmp[chr]++
          else break
        }
        else tmp[chr] = 1
      }

      if (areEqual (tmp,tMap)){
        answer.push(start)
        i = j - 1
      }

    }
  }
  return answer
}

//function to compare arrays
function areEqual(arr1,arr2){
  if (arr1.length != arr2.length) return false
  for (var i in arr1)
    if (arr1[i] != arr2[i]) return false
  return true
}

</script>

出力：

console.log(matchT("edf","ghjfedabcddef"))
[3, 10]
于 2013-08-01T22:02:39.800 に答える
0

与えられた例について考えてみましょう。文字列 S: abcdef 文字列 T: efd

部分文字列 T に存在する文字で構成される HashSet を作成します。したがって、セットは .

部分文字列 T: 1e1f1dのラベルを生成します。(各文字の出現回数 + 文字自体、カウント ソートと同様の手法を使用して実行できます)

ここで、部分文字列の長さを入力するためのラベルを生成する必要があります。

文字 a を持つ最初の位置から始めましょう。存在しないため、部分文字列を作成せず、次の文字 b に移動します。同様に、文字 c に移動し、次に d で停止します。

d は HashSet に存在するため、文字が出現するたびに (部分文字列の長さの) ラベルの生成を開始します。これを別の関数で実行して、カウント配列をクリアしないようにすることができます (これを行うと、複雑さが O(m*n) から O(m+n) に軽減されます)。任意の時点で入力文字列が部分文字列 T で構成されていない場合は、次の位置からラベルの生成を開始できます (ブレークが発生するまでの位置はアナグラムの一部になることができないため)。

したがって、ラベルを生成することで、線形 O(m+n) 時間の複雑さで問題を解決できます。

m: 入力文字列の長さ、n: サブ文字列の長さ。

于 2013-11-20T02:30:57.123 に答える
0

アルファベットが大きすぎない場合 (ASCII など)、文字列を処理するためにハッシュを使用する必要はありません。

アルファベットと同じサイズの大きな配列を使用するだけで、存在チェックは になりO(1)ます。したがって、アルゴリズム全体は になりO(m+n)ます。

于 2013-07-31T00:44:47.663 に答える