文字列 "aaa"〜 "3 [a]"

Question

は、文字列sを与え、 "aaa"〜 "3 [a]"の形式でエンコードします。コード化された文字列の長さが最短になります。 例： "abbabbは" "2 [A2 [B]]"

更新する：ここで、C++での私のコードですが、それは遅いです：文字列が小文字のみ

アップデートが含まれているとします。現在の文字列が繰り返し文字列で結合されているかどうかを計算するのにKMPを使用して改善が行われていることがわかります。

// this function is used to check if a string is combined by repeating a substring. 
// Also Here can be replaced by doing KMP algorithm for whole string to improvement 

bool checkRepeating(string& s, int l, int r, int start, int end){ 
    if((end-start+1)%(r-l+1) != 0) 
     return false; 
    int len = r-l+1; 
    bool res = true; 
    for(int i=start; i<=end; i++){ 
     if(s[(i-start)%len+l] != s[i]){ 
      res = false; 
      break; 
     } 
    } 
    return res; 
} 

// this function is used to get the length of the current number 
int getLength(int l1, int l2){ 
    return (int)(log10(l2/l1+1)+1); 
} 

string shortestEncodeString(string s){ 
    int len = s.length(); 

    vector< vector<int> > res(len, vector<int>(len, 0)); 
    //Initial the matrix 
    for(int i=0; i<len; i++){ 
     for(int j=0; j<=i; j++){ 
      res[j][i] = i-j+1; 
     } 
    } 

    unordered_map<string, string> record; 

    for(int i=0; i<len; i++){ 
     for(int j=i; j>=0; j--){ 

      string temp = s.substr(j, i-j+1); 
/* if the current substring has showed before, then no need to compute again 
* Here is a example for this part: if the string is "abcabc". 
* if we see the second "abc", then no need to compute again, just use the 
* result from first "abc". 
**/ 
      if(record.find(temp) != record.end()){ 
       res[j][i] = record[temp].size(); 
       continue; 
      } 
      string ans = temp; 
      for(int k=j; k<i; k++){ 

       string str1 = s.substr(j, k-j+1); 
       string str2 = s.substr(k+1, i-k); 
       if(res[j][i] > res[j][k] + res[k+1][i]){ 
        res[j][i] = res[j][k]+res[k+1][i]; 
        ans = record[str1] + record[str2]; 
       } 

       if(checkRepeating(s, j, k, k+1, i) == true && res[j][i] > 2+getLength(k-j+1, i-k)+res[j][k]){ 
        res[j][i] = 2+getLength(k-j+1, i-k)+res[j][k]; 
        ans = to_string((i-j+1)/(k-j+1)) + '[' + record[str1] +']'; 
       } 
      } 
      record[temp] = ans; 
     } 

    } 

    return record[s]; 
} 

Answer 1

質問文で始めるのはあまりありませんが、簡単に説明するとJavaScriptを使用して簡単に突き刺しました。コメントはコードに含まれていますが、基本的に隣り合った要素の結合、ランレングスのチェック、隣接する要素の結合、そして1つの要素が残るまでのオンとオフの交互の段階があります。

私はこのことができます願っています。

function encode(str) { 
 
    var tmp = str.split(''); 
 
    var arr = []; 
 

 
    do { 
 
    if (tmp.length === arr.length) { 
 
     // Join adjacent elements 
 
     arr.length = 0; 
 
     for (var i = 0; i < tmp.length; i += 2) { 
 
     if (i < tmp.length - 1) { 
 
      arr.push(tmp[i] + tmp[i + 1]); 
 
     } else { 
 
      arr.push(tmp[i]); 
 
     } 
 
     } 
 
     tmp.length = 0; 
 
    } else { 
 
     // Swap arrays and clear tmp 
 
     arr = tmp.slice(); 
 
     tmp.length = 0; 
 
    } 
 

 
    // Build up the run-length strings 
 
    for (var i = 0; i < arr.length;) { 
 
     var runlength = runLength(arr, i); 
 
     if (runlength > 1) { 
 
     tmp.push(runlength + '[' + arr[i] + ']'); 
 
     } else { 
 
     tmp.push(arr[i]); 
 
     } 
 
     i += runlength; 
 
    } 
 
    console.log(tmp); 
 
    } while (tmp.length > 1); 
 
    return tmp.join(); 
 
} 
 

 
// Get the longest run length from a given index 
 
function runLength(arr, ind) { 
 
    var count = 1; 
 
    for (var i = ind; i < arr.length - 1; i++) { 
 
    if (arr[i + 1] === arr[ind]) { 
 
     count++; 
 
    } else { 
 
     break; 
 
    } 
 
    } 
 
    return count; 
 
}

<input id='inp' value='abbabb'> 
 
<button type="submit" onClick='javascript:document.getElementById("result").value=encode(document.getElementById("inp").value)'>Encode</button> 
 
<br> 
 
<input id='result' value='2[a2[b]]'>