Алгоритм для преобразования строки из одного формата в другой

Question

Я искал проблему, которая заявляла, чтобы преобразовать строки, как показано ниже.

s = "3[a]2[bc]", return "aaabcbc". 
s = "3[a2[c]]", return "accaccacc". 
s = "2[abc]3[cd]ef", return "abcabccdcdcdef". 

Я смог понять, как это сделать.

Я думал, есть ли способ сделать это в обратном. когда задана строка вроде abcabccdcdcdef Я понимаю, что может быть много возможностей представления. Я смотрел, можем ли мы сделать это в представлении, которое берет наименьшее количество памяти (не алгоритмическое, а конечная строка).

Answer 1

для максимальной эффективности, мы хотим иметь как можно меньше сокращения. Я думаю, что я хотел бы сделать что-то вроде этого (это может быть не самый эффективный алгоритм):

s = "whateverwhateveryouwantwantwantababababababababc" 
possibilities = [] 
repeats = [] 
def findRepeats(repeats, s, length): 
    for i in range(0, len(s) - 2 * length + 1): 
     if s[i:i+length] == s[i+length:i+2*length]: 
      trackInd = i+length 
      times = 2 
      while trackInd+2*length <= len(s): 
       if (s[trackInd:trackInd+length]==s[trackInd+length:trackInd+2*length]): 
        times += 1 
       else: break 
       trackInd += length 

      repeats.append((i, times, s[i:i+length])) 

    return repeats 

for i in range(0, len(s)): 
    repeats = findRepeats(repeats, s, i) 

def formPossibility(repeats, s): 
    build = "" 
    i = 0 
    while i < len(s): 
     pass = True 
     for repeat in repeats: 
      if repeat[0] == i: 
       pass = False 
       build += repeat[1] + "[" 
       build += repeat[2] + "]" 
       break 

     if pass: 
      build += s[i] 

# I didn't finish this but you would loop through all the repeats and test 
# them to see if they overlap, and then you would take all the posibilities 
# of different ways to make them so that some are there, and some are not. 
# in any case, I think that you get the idea. 
# I couldn't finish this because I am doing the coding on stackoverflow and 
# its like so painful and so hard to debug. also I don't have enough time sorry 

Answer 2

Не знаю, если это является наиболее эффективным, или если он эффективен на всех, но вот мой подход с использованием JS.

function format(pattern, length, times) { 
 
    var result = ""; 
 
    if (times == 0) { 
 
     result = pattern; 
 
    } else { 
 
     result = (times + 1).toString() + "[" + pattern + "]"; 
 
    } 
 
    return result; 
 
} 
 

 
function encode(input) { 
 
    var result = ""; 
 
    var pattern = { length: 1, times: 0 }; 
 
    var i = 1; 
 
    while (i <= input.length/2) { 
 
     var subpattern = input.substr(0, i); 
 
     var j = 0; 
 
     while (input.substr(i + j * i, i) == subpattern && j + i < input.length) { 
 
      j++; 
 
     } 
 
     if (i * j > pattern.length * pattern.times) { 
 
      pattern.length = i; 
 
      pattern.times = j; 
 
     } 
 
     i++; 
 
    } 
 
    if (pattern.length > 1) { 
 
     result = format(encode(input.substr(0, pattern.length)), pattern.length, pattern.times); 
 
    } else { 
 
     result = format(input.substr(0, pattern.length), pattern.length, pattern.times); 
 
    } 
 
    if (pattern.length + pattern.length * pattern.times < input.length) { 
 
     result += encode(input.substr(pattern.length + pattern.length * pattern.times, input.length)); 
 
    } 
 
    return result; 
 
}