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)，因為我們沒有使用任何額外的空間。

我們學習了兩種解決問題的方法。第一種方法進行字串旋轉並在旋轉後的字串中訪問字串字元。它具有更高的時間和空間複雜度。第二種方法是第一種方法的最佳化版本，它操縱索引並從原始字串訪問字元。