后缀数组算法

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
// Structure of suffixes
struct Suffix {
   int index;
   string suff;
};
// Function to compare two suffixes for sorting
bool strCompare(Suffix a, Suffix b) {
   return a.suff < b.suff;
}
// Function to fill the suffix array
int* fillSuffixArray(string txt, int n) {
   Suffix* suffixes = new Suffix[n];
   // Storing suffixes and indexes in an array 
   for (int i = 0; i < n; i++) {
      suffixes[i].index = i;
      suffixes[i].suff = txt.substr(i, n - i);
   }
   // Sorting the suffixes 
   sort(suffixes, suffixes+n, strCompare);
   // Store indexes of all sorted suffixes in suffix array
   int* suffixArr = new int[n];
   for (int i = 0; i < n; i++)
      suffixArr[i] = suffixes[i].index;
   // Deallocate the dynamic memory
   delete[] suffixes;
   return suffixArr;
}
// binary search on the suffix array and find all occurrences of pattern
void suffixArraySearch(string pat, string txt, int* suffixArr, int n) {
   int m = pat.length();
   // binary search for the pattern 
   int l = 0, r = n - 1;
   while (l <= r) {
      int mid = l + (r - l) / 2;
      string substr = txt.substr(suffixArr[mid], m);
      if (pat == substr) {
         cout << "Pattern found at index: " << suffixArr[mid] << endl;
         // Move to the left of mid
         int temp = mid - 1;
         while (temp >= 0 && txt.substr(suffixArr[temp], m) == pat) {
            cout << "Pattern found at index: " << suffixArr[temp] << endl;
            temp--;
         }
         // Move to the right of mid
         temp = mid + 1;
         while (temp < n && txt.substr(suffixArr[temp], m) == pat) {
            cout << "Pattern found at index: " << suffixArr[temp] << endl;
            temp++;
         }
         return;
      }
      if (pat < substr) r = mid - 1;
      else l = mid + 1;
   }
   cout << "Pattern not found" << endl;
}
int main() {
   string txt = "AAAABCAEAAABCBDDAAAABC";
   // pattern to be searched
   string pat = "AAABC";
   int n = txt.length();
   int* suffixArr = fillSuffixArray(txt, n);
   suffixArraySearch(pat, txt, suffixArr, n);
   delete[] suffixArr;  
   return 0;
} 

import java.util.Arrays;
public class Main {
   // Structure of suffixes
   static class SuffixCmpr implements Comparable<SuffixCmpr> {
      int index;
      String suff;
      // Constructor
      public SuffixCmpr(int index, String suff) {
         this.index = index;
         this.suff = suff;
      }
      // to sort suffixes alphabetically
      public int compareTo(SuffixCmpr other) {
         return this.suff.compareTo(other.suff);
      }
   }
   // method to build a suffix array
   public static int[] fillsuffixArray(String s) {
      int n = s.length();
      SuffixCmpr[] suffixes = new SuffixCmpr[n];
      // Create and sort suffixes
      for (int i = 0; i < n; i++) {
         suffixes[i] = new SuffixCmpr(i, s.substring(i));
      }
      Arrays.sort(suffixes);
      // Store indexes of all sorted suffixes
      int[] fillsuffixArray = new int[n];
      for (int i = 0; i < n; i++) {
         fillsuffixArray[i] = suffixes[i].index;
      }
      return fillsuffixArray;
   }
   // method to search a pattern in a text using suffix array
   public static void suffixArraySearch(String pattern, String txt, int[] suffArr) {
      int n = txt.length();
      int m = pattern.length();
      // binary search for the pattern in the text using suffix array
      int l = 0, r = n - 1;
      while (l <= r) {
         int mid = l + (r - l) / 2;
         int res = pattern.compareTo(txt.substring(suffArr[mid], Math.min(suffArr[mid] + m, n)));
         if (res == 0) {
            System.out.println("Pattern found at index: " + suffArr[mid]);
            // Move to previous suffix in the sorted array
            int temp = mid - 1;
            while (temp >= 0 && txt.substring(suffArr[temp], Math.min(suffArr[temp] + m, n)).equals(pattern)) {
                System.out.println("Pattern found at index: " + suffArr[temp]);
                temp--;
            }
            // Move to next suffix in the sorted array
            temp = mid + 1;
            while (temp < n && txt.substring(suffArr[temp], Math.min(suffArr[temp] + m, n)).equals(pattern)) {
                System.out.println("Pattern found at index: " + suffArr[temp]);
                temp++;
            }
            return;
         }
         if (res < 0) r = mid - 1;
         else l = mid + 1;
      }
      System.out.println("Pattern not found");
   }
   public static void main(String[] args) {
      String txt = "AAAABCAEAAABCBDDAAAABC";
      String pattern = "AAABC";
      // Filling the suffix array
      int[] suffArr = fillsuffixArray(txt);
      // Calling method to Search pattern in suffix array
      suffixArraySearch(pattern, txt, suffArr);
   }
}

def fill_suffix_array(txt):
    # Array of tuples, each tuple stores the index and suffix
    suffixes = [(i, txt[i:]) for i in range(len(txt))]
    # Sort the suffixes
    suffixes.sort(key=lambda x: x[1])
    # Return the list of indices after sorting
    return [suff[0] for suff in suffixes]

def suffixArraySearch(pat, txt, suffix_arr):
    n = len(txt)
    m = len(pat)
    # Iterate over the suffix array
    for i in range(n):
        if txt[suffix_arr[i]:min(suffix_arr[i] + m, n)] == pat:
            print(f"Pattern found at index: {suffix_arr[i]}")

def main():
    txt = "AAAABCAEAAABCBDDAAAABC"
    pat = "AAABC"
    suffix_arr = fill_suffix_array(txt)
    suffixArraySearch(pat, txt, suffix_arr)

if __name__ == "__main__":
    main()