Эффективно найти символ в строке, образованной повторяющейся подстрокой целым числом

Question

Дана строка s и целое число k.Какой самый эффективный способ найти k-й символ (0 индекс) в новой строке, образованной из s, со следующим правилом (продемонстрировано в качестве примеров):

При итерации каждого символа в s слева направовсякий раз, когда встречается целое число (гарантированное значение от 2 до 9), вы повторяете подстроку до этой точки этим целым числом.

ex) (s = 'a2', k = 1): из s-> 'aa', вернуть 'a', поскольку он находится по индексу 1 во вновь сформированной строке

ex) (s = 'a2b3', k = 2): from s -> 'aabaabaab', return 'b '

Очевидно, что наивное решение состоит в том, чтобы сначала сгенерировать новую строку и внести в нее индекс.Однако, учитывая случаи, когда чисел много, а строка достигает огромного размера, определенно должно быть лучшее решение для возврата только k-го символа.Я слишком долго боролся с этим, и любая помощь будет признательна!

Answer 1

Если вы знаете, что какая-то строка s является другой строкой t, повторенной n раз, тогда символ с индексом k в строке s равен символу с индексом k2 = k mod t.length в строке t.Мы можем использовать это для решения этой задачи:

1. Определить длину строки результата:

   len = 0
   for each character ch in s
       if ch is digit
           len = len * digit
       else
           len = len + 1
   

2. Итерация в обратном порядке черезстрока

    reverseS = reverse(s)
    curLen = len
    for each character ch in reverseS
        if ch is digit
            curLen = curLen / digit
            k = k mod curLen 
        else 
            if k == (curLen-1) then return ch as answer
            curLen = curLen - 1
   

В результате вам вообще не нужна дополнительная память (на самом деле O(1)), а алгоритм имеет O(n) сложность по времени, где n - это размерстрока ввода.

Пример кода C ++: https://ideone.com/l8JxdQ

Answer 2

Лучшее, что я могу придумать, - это только частичное генерирование строки.Учитывая подстроку и количество повторений, вы, конечно, можете просто использовать modulo и определить, где вы попадете в подстроку.Проблема здесь в том, что вы повторяете всю подстроку до того момента, когда вы видите число, включая любые предыдущие дубликаты подстрок.

В принципе, я не могу придумать математического способа сделать это, я думаю, вам всегда нужно будет генерировать строку до итерации до той, которая вызовет s.length() > k, или до последней цифрыво входной строке, в зависимости от того, что наступит раньше.Затем вы можете k%s.length() найти правильный символ.

В C ++ это выглядит так:

char getK(string s, int k){
  string genString = "";
  string tempString = "";
  string digits = "0123456789";
  char c = '\0';
  const char * cc = &c;
  for (int i = 0; i < s.length(); i++){
    c = s[i];
    if (digits.find(c) != std::string::npos ){ // Digit
      if (i == s.length()-1 || k < genString.length()*atoi(cc)){ // Final digit or the next substring will contain genString[k]
        return genString[k%genString.length()]; // Modulo to find character location
      }
      tempString = genString;
      genString = "";
      for (int i = 0; i < atoi(cc); i++){
        genString += tempString;
      }
    } else { // Not a digit
      genString += c;
    }
    if (genString.length() > k) return genString[k]; // genString contains genString[k]
  }

  return genString[k]; // Silence compiler warnings
}

И может использоваться следующим образом:

int main()
{
  string s = "a2b3c7g3g8r4w5rf5";
  for (int k = 0; k < 20; k++){
    cout << i << ": " << getK(s, k) << endl;
  }
}

Если вы поместите в цикл некоторые операторы cout, вы увидите, что он генерирует только столько строки, сколько ему необходимо.