C++程序：用于在常数时间内查询给定字符串的旋转和第K个字符

---

在这个问题中，我们需要对字符串执行给定的查询。我们可以通过以不同的方式进行字符串旋转并使用其索引访问所需的字符来解决问题。

问题陈述 – 我们给定长度为N的字符串str和大小为M的数组'que'，其中包含查询。我们需要根据以下条件执行数组中给定的查询。

• (1, x) – 对字符串进行x次左旋转。

• (2, x) – 在输出中显示第x个字符。

示例

输入

que[][2] = {{1, 2}, {2, 1}, {1, 1}, {2, 3}}, str = "ersfd5tr"

输出

s, 5

解释

• 执行第一个查询后，字符串变为“sfd5trer”。

• 在第二个查询中，它显示更新后的字符串中第1个位置的字符。因此，该字符为“s”。

• 在第三个查询中，它进行1次左旋转，结果字符串将为“fd5trers”。

• 最后一个查询显示第3个位置的字符，即5。

输入

que[][2] = {{1, 5}, {2, 1}, {2, 2}, {2, 3}}, str = "tutorialspoint"

输出

i, a, l

解释

• 执行第一个查询后，字符串变为“ialspointtutor”。

• 在第二个查询中，它显示“i”。

• 第三个查询显示“a”，第四个查询显示“l”。

方法1

在这种方法中，如果我们得到(1, x)查询对，我们将旋转字符串。我们将使用substr()方法获取子字符串并从第x个索引旋转给定字符串。

算法

步骤1 – 开始遍历查询数组。

步骤2 – 如果查询对中的第一个元素为1，则对字符串进行x次左旋转并更新字符串。我们可以获取字符串的右侧部分和左侧部分。之后，我们可以合并right + left来旋转字符串。

步骤3 – 如果查询对中的第一个元素为2，则从查询对中访问字符索引。

步骤4 – 通过访问给定索引处的字符来打印字符串的字符。

示例

#include <bits/stdc++.h>
using namespace std;

void executeQueries(string str, int str_len, int que[][2], int q_size){
    // Traverse query
    for (int p = 0; p < q_size; p++) {
        // For string rotation
        if (que[p][0] == 1) {
            // rotating str by que[p][1]
            str = str.substr(que[p][1], str_len - que[p][1]) + str.substr(0, que[p][1]);
        } else {
            int x = que[p][1];
            // Show character in the output
            cout << str[x - 1] << endl;
            ;
        }
    }
}

int main() {
    string str = "ersfd5tr";
    int str_len = str.length();
    int que[][2] = {{1, 2}, {2, 1}, {1, 1}, {2, 3}};
    int q_size = sizeof(que) / sizeof(que[0]);
    executeQueries(str, str_len, que, q_size);
    return 0;
}

输出

s
5

时间复杂度 – O(M*N)，因为我们遍历查询数组并在其中获取子字符串。

空间复杂度 – O(N)，因为我们存储子字符串。

方法2

在这种方法中，我们通过根据给定查询更新它来操纵索引值。当我们需要打印字符时，我们根据更新的索引值访问字符。

算法

步骤1 – 定义变量'ind'并初始化为0以存储更新的索引。

步骤2 – 在遍历查询时，如果我们需要旋转字符串，则通过添加总旋转次数并将其模26来更新'ind'值。

步骤3 – 如果我们需要打印字符，我们可以将'x'值添加到'ind'值中并将其模26。获取更新的索引后，我们可以打印字符。

示例

#include <bits/stdc++.h>
using namespace std;

void executeQueries(string str, int str_len, int que[][2], int q_size) {
    // Starting x_ind
    int ind = 0;
    // Traverse query
    for (int p = 0; p < q_size; p++) {
        // For string rotation
        if (que[p][0] == 1) {
            // Change x_ind according to the array element value
            ind = (ind + que[p][1]) % str_len;
        } else {
            int x = que[p][1];
            // Find the index of X in the current rotation
            int x_ind = (ind + x - 1) % str_len;
            // Show character in the output
            cout << str[x_ind] << endl;
        }
    }
}
int main() {
    string str = "ersfd5tr";
    int str_len = str.length();
    int que[][2] = {{1, 2}, {2, 1}, {1, 1}, {2, 3}};
    int q_size = sizeof(que) / sizeof(que[0]);
    executeQueries(str, str_len, que, q_size);
    return 0;
}

输出

s
5

时间复杂度 – O(M)，因为我们遍历查询。

空间复杂度 – O(1)，因为我们没有使用任何额外的空间。

我们学习了两种解决问题的方法。第一种方法进行字符串旋转并在旋转后的字符串中访问字符串字符。它具有更高的时间和空间复杂度。第二种方法是第一种方法的优化版本，它操纵索引并从原始字符串访问字符。