查找给定字符串的后缀数组，该字符串不包含重复字符

---

在这个问题中，我们将找到给定字符串的后缀数组。由于输入字符串包含不同的字符，我们可以使用它们的第一个字符对所有字符串的后缀进行排序。

问题陈述 - 我们给定一个包含不同字母字符的字符串，我们需要找到给定字符串的后缀数组。字符串的后缀数组是一个排序数组，包含给定字符串的所有后缀。

示例

输入

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)，因为我们使用了数组。