グループ隣接するサブストリングとカウントを見つける

Question

こんにちはこれは私がC/C++でコードを書くためにインタビューで尋ねられた質問です。

文字列を指定すると、可能な操作が提供されます。 私たちは、グループ例えばABCABCBCため、隣接するサブストリングは、すべての可能な選択肢の中で 2ABC1BCまたは1ABCA2BC

として圧縮することができることができ、タスクは、最小の長さと結果の文字列を見つけることです。

複数の解決策がある場合は、辞書順に最小の文字列を返します。 1FLF3LAF

私はそれが接尾辞木、または順列/再帰メソッドを使用して行うことができるだけにロジックを取得することはできません知っている： だから、上記の例のためのソリューションは、2ABC1BC

別の例は FLFLAFLAFLAF 解決策になるだろうどのように。助けてください ？入力接頭辞を圧縮し、再帰的に入力の残りの部分に自分自身を呼び出す

Answer 1

アルゴリズムは（live demo）を行うことができます。このソリューションを書くことだけのシンプルであること

#include <iostream> 
#include <string> 
#include <limits> 
#include <cstring> 
using namespace std; 

// determine how many times the prefix of specific length is repeated in the input 
int repetitions(string const & input, int prefix_length) 
{ 
    int i = 1; 
    while (
     (i + 1) * prefix_length <= input.size() && 
     memcmp(input.data(), input.data() + i * prefix_length, prefix_length) == 0 
     ) 
    { 
     ++i; 
    } 

    return i; 
} 

// recursively compress input and return compressed string 
string compress(string const & input) 
{ 
    // recursion termination 
    if (input.empty()) 
     return string(); 

    string best; 
    int best_length = numeric_limits<int>::max(); 

    // try various prefix lengths 
    for (int prefix_length = 1; prefix_length <= input.length(); ++prefix_length) 
    { 
     const auto max_count = repetitions(input, prefix_length); 

     // try various number of repetitions up to the maximum possible 
     for (int count = 1; count <= max_count; ++count) 
     { 
      // the candidate is compressed prefix and the rest of input compressed recursively 
      const auto current = 
       to_string(count) + input.substr(0, prefix_length) + // compressed prefix 
       compress(input.substr(prefix_length * count)); // the rest of input compressed recursively 

      // store candidate if it is better than the currently best 
      if (current.length() < best_length) 
      { 
       best = current; 
       best_length = current.length(); 
      } 
     } 
    } 

    return best; 
} 

int main() 
{ 
    string input; 
    cin >> input; 
    cout << compress(input); 
    return 0; 
} 

注意。非常に効率的ではなく、長い入力に対してはスタックオーバーフローが発生します。