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’。
在第三个查询中，它进行了一次向左的旋转，结果字符串将变为’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个索引开始旋转给定的字符串。 th 索引。

算法

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

步骤2 - 如果查询对中的第一个元素为1，将字符串左旋x次并更新字符串。我们可以取字符串的右半部分和左半部分，然后将右半部分和左半部分合并以旋转字符串。

步骤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 - 在遍历查询时，如果我们需要旋转字符串，则通过将总旋转次数添加到“ind”值并将其对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;
}