查詢給定字串的字尾陣列，該字串不包含重複字元

---

在這個問題中，我們將找到給定字串的字尾陣列。由於輸入字串包含不同的字元，我們可以使用它們的第一個字元對所有字串的字尾進行排序。

問題陳述 - 我們給定一個包含不同字母字元的字串，我們需要找到給定字串的字尾陣列。字串的字尾陣列是一個排序陣列，包含給定字串的所有後綴。

示例

輸入

str = "point";

輸出

2 3 1 0 4

解釋

• 字串的所有後綴是 'point'、'oint'、'int'、'nt' 和 't'。

• 字尾的排序順序是 'int'、'nt'、'oint'、'point' 和 't'。

• 我們列印了字尾的起始索引，根據字尾的排序順序為 2 3 1 0 4。

輸入

str = "dbce";

輸出

1 2 0 3

解釋

• 所有後綴是 'e'、'ce'、'bce' 和 'dbce'。

• 字尾的排序順序是 'bce'、'ce'、'dbce' 和 'e'。

• 根據排序順序，字尾的索引是 1、2、0、2。

方法 1

在這種方法中，我們將使用陣列跟蹤字串中字元的存在。之後，我們將計算累積頻率，並根據該頻率獲得排序順序中字尾的起始索引。

演算法

步驟 1 - 定義長度為 26 的 'freq' 陣列，並將所有元素初始化為零。

步驟 2 - 統計每個字元的頻率並將其儲存在 freq 陣列中。

步驟 3 - 現在，遍歷 freq 陣列並將前一個元素的值新增到當前元素。

步驟 4 - 定義 'move' 陣列並將第一個元素初始化為零。在 move 陣列中，我們需要透過將每個元素移動到下一個索引來儲存 freq 陣列的每個元素。這意味著我們需要對所有元素執行 move[p+1] = freq[p]。

步驟 5 - 現在，定義 'indexs' 陣列來儲存排序字尾的索引。

步驟 6 - 反向遍歷字串以獲取每個字尾。在迴圈中，從 'move' 陣列中獲取當前字元的秩，並將 'p' 儲存在該特定索引處。

步驟 7 - 列印 'indexs' 陣列的所有值。

示例

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

void printSuffixArray(string alpha, int len) {
   // Calculate the frequency of each character of the string
   int freq[26] = {0};
   for (int p = 0; p < len; p++) {
      freq[alpha[p] - 'a']++;
   }
   // Finding the cumulative frequency of each character
   for (int p = 1; p < 26; p++) {
      freq[p] = freq[p] + freq[p - 1];
   }
   int move[26];
   move[0] = 0;
   for (int p = 0; p < 25; p++) {
      move[p + 1] = freq[p];
   }
   int indexs[len] = {0};
   // Traverse the string in reverse order
   for (int p = len - 1; p >= 0; p--) {
      // Storing suffix array in indexs[]
      indexs[move[alpha[p] - 'a']] = p;
   }
   // Print sorted suffix
   for (int p = 0; p < len; p++)
      cout << indexs[p] << " ";
}
int main(){
   string str = "point";
   int len = str.length();
   printSuffixArray(str, len);
   return 0;
}

輸出

2 3 1 0 4

時間複雜度 - O(N)，因為我們遍歷了字串。

空間複雜度 - O(N)，因為我們使用了陣列。