C++ 找到给定字符串的后缀数组，其中没有重复字符

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

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

示例

输入

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 - 定义长度为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;
}