0

私はint配列を持っていますint[] A = {3, 5, 7, 3, 3, 5};

定義により：

prefix_suffix_set は、、 および次のような(P, S)インデックスのペアです。0 ≤ PS < N

  • シーケンス内で発生するすべての値は、シーケンスA[0], A[1], ..., A[P]内でも発生しますA[S], A[S + 1], ..., A[N − 1]。
  • シーケンス内で発生するすべての値は、シーケンスA[S], A[S + 1], ..., A[N − 1]内でも発生しますA[0], A[1], ..., A[P]。

私の質問は次のとおりです:プレフィックスサフィックスセットのリストはどれですか?

4

2 に答える 2

1

考えられる解決策は次のとおりです。

(P,S) -- prefix set - suffix set
(1,4) -- {3,5} - {3,5}
(1,3) -- {3,5} - {3,5} 
(2,2) -- {3,5,7} - {3,5,7}

は必須ではないためP <= S、これらも許可されます (そうでない場合は除外されます)。

(2,1) -- the same as above, just having all the possibilities
(2,0) -- where P >= 2 and S <=2
(3,2) 
(3,1) 
(3,0)
(4,2)
(4,1)
(4,0)
(5,2)
(5,1)
(5,0)

したがって、結果は上記のタプルのセットになります。あなたの配列のサイズのように、Nだと思います。6

于 2013-09-10T15:03:49.823 に答える
1

C++ のコード:

#include <iostream>
#include <set>

using std::set;
using std::cout;
using std::endl;

int main() {

  int A[6] = { 3, 5, 7, 3, 3, 5 };

  int countPS = 0;

  for ( int i = 1; i <= 6; i++ ) {

    set<int> P;
    P.insert( A , A + i );

    for ( int j = 5; j >= 0; j-- ) {

       set<int> S;
       S.insert( A + j, A + 6 );

       if ( P == S )
          countPS++;
    } 
  }
  cout << "The number of elements in list (P,S) = " << countPS << endl;

  return 0;
}

プログラム出力:

Success time: 0 memory: 3476 signal:0
The number of elements in list (P,S) = 14

http://ideone.com/8adJ1A

于 2013-09-10T14:17:48.907 に答える