在由整数重复子串形成的字符串中有效地查找字符

Question

给定一个字符串 s 和整数 k。什么是最 space 在由 s 形成的新字符串中使用以下规则（作为示例演示）查找第 k（0 索引）字符的最有效方法：

从左到右迭代 s 中的每个字符时，每当遇到一个整数（保证在 2 到 9 之间）时，您将重复该整数到该点的子字符串。

ex) (s = 'a2', k = 1) : 从 s -> 'aa', return 'a' 因为它在新形成的字符串

中位于索引 1

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

显然，天真的解决方案是先生成新字符串并对其进行索引。但是，考虑到数字很多并且字符串达到巨大大小的情况，当然必须有更好的解决方案 return 只是第 k 个字符。我已经为此苦苦挣扎了太久，我们将不胜感激！

Answer 1

我能想到的最好的办法就是只生成部分字符串。给定一个子字符串和重复它的次数，您当然可以只使用 modulo 并确定您将落在子字符串中的位置。这里的问题是，您要重复整个子串，直到您看到一个数字，包括任何先前的子串重复。

基本上，我想不出一种数学方法来执行此操作，我认为您始终需要生成字符串，直到导致 s.length() > k 的迭代之前的迭代或最后一次迭代输入字符串中的数字，以先到者为准。然后你可以k%s.length()找到正确的字符。

在 C++ 中看起来像这样：

char getK(string s, int k){
  string genString = "";
  string tempString = "";
  string digits = "0123456789";
  char c = '[=10=]';
  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 语句，您可以看到它只生成所需的字符串。

Answer 2

如果您知道某个字符串 s 是另一个字符串 t 重复 n 次，那么字符串 s 中索引为 k 的字符相等到字符串 t 中索引为 k2 = k mod t.length 的字符。我们可以用它来解决这个任务：

判断结果字符串的长度：

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

以相反的顺序遍历字符串

 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

在由整数重复子串形成的字符串中有效地查找字符

Efficiently find character in a string formed by repeated substring by integer

algorithm

memory-efficient