java - 为 int 数组设置 Preffix_Suffix [编程]

Question

我有整数数组int[] A = {3, 5, 7, 3, 3, 5};

根据定义：

prefix_suffix_set 是一对索引(P, S)，例如0 ≤ P，S < 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]。

我的问题是：哪个是前缀后缀集列表？

Answer 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，就像你的数组的大小。

Answer 2

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