آرایه پسوندی (Suffix Array) — به زبان ساده

1// Naive algorithm for building suffix array of a given text 
2#include <iostream> 
3#include <cstring> 
4#include <algorithm> 
5using namespace std; 
6  
7// Structure to store information of a suffix 
8struct suffix 
9{ 
10    int index; 
11    char *suff; 
12}; 
13  
14// A comparison function used by sort() to compare two suffixes 
15int cmp(struct suffix a, struct suffix b) 
16{ 
17    return strcmp(a.suff, b.suff) < 0? 1 : 0; 
18} 
19  
20// This is the main function that takes a string 'txt' of size n as an 
21// argument, builds and return the suffix array for the given string 
22int *buildSuffixArray(char *txt, int n) 
23{ 
24    // A structure to store suffixes and their indexes 
25    struct suffix suffixes[n]; 
26  
27    // Store suffixes and their indexes in an array of structures. 
28    // The structure is needed to sort the suffixes alphabatically 
29    // and maintain their old indexes while sorting 
30    for (int i = 0; i < n; i++) 
31    { 
32        suffixes[i].index = i; 
33        suffixes[i].suff = (txt+i); 
34    } 
35  
36    // Sort the suffixes using the comparison function 
37    // defined above. 
38    sort(suffixes, suffixes+n, cmp); 
39  
40    // Store indexes of all sorted suffixes in the suffix array 
41    int *suffixArr = new int[n]; 
42    for (int i = 0; i < n; i++) 
43        suffixArr[i] = suffixes[i].index; 
44  
45    // Return the suffix array 
46    return  suffixArr; 
47} 
48  
49// A utility function to print an array of given size 
50void printArr(int arr[], int n) 
51{ 
52    for(int i = 0; i < n; i++) 
53        cout << arr[i] << " "; 
54    cout << endl; 
55} 
56  
57// Driver program to test above functions 
58int main() 
59{ 
60    char txt[] = "banana"; 
61    int n = strlen(txt); 
62    int *suffixArr = buildSuffixArray(txt,  n); 
63    cout << "Following is suffix array for " << txt << endl; 
64    printArr(suffixArr, n); 
65    return 0; 
66}

1// This code only contains search() and main. To make it a complete running 
2// above code or see https://ide.geeksforgeeks.org/oY7OkD 
3  
4// A suffix array based search function to search a given pattern 
5// 'pat' in given text 'txt' using suffix array suffArr[] 
6void search(char *pat, char *txt, int *suffArr, int n) 
7{ 
8    int m = strlen(pat);  // get length of pattern, needed for strncmp() 
9  
10    // Do simple binary search for the pat in txt using the 
11    // built suffix array 
12    int l = 0, r = n-1;  // Initilize left and right indexes 
13    while (l <= r) 
14    { 
15        // See if 'pat' is prefix of middle suffix in suffix array 
16        int mid = l + (r - l)/2; 
17        int res = strncmp(pat, txt+suffArr[mid], m); 
18  
19        // If match found at the middle, print it and return 
20        if (res == 0) 
21        { 
22            cout << "Pattern found at index " << suffArr[mid]; 
23            return; 
24        } 
25  
26        // Move to left half if pattern is alphabtically less than 
27        // the mid suffix 
28        if (res < 0) r = mid - 1; 
29  
30        // Otherwise move to right half 
31        else l = mid + 1; 
32    } 
33  
34    // We reach here if return statement in loop is not executed 
35    cout << "Pattern not found"; 
36} 
37  
38// Driver program to test above function 
39int main() 
40{ 
41    char txt[] = "banana";  // text 
42    char pat[] = "nan";   // pattern to be searched in text 
43  
44    // Build suffix array 
45    int n = strlen(txt); 
46    int *suffArr = buildSuffixArray(txt, n); 
47  
48    // search pat in txt using the built suffix array 
49    search(pat, txt, suffArr, n); 
50  
51    return 0; 
52}