This is the main function that takes a string 'txt' of size n as an argument, builds and return the suffix array for the given string
| 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 |
| 22 | vector<int> buildSuffixArray(string 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].rank[0] = txt[i] - 'a'; |
| 34 | suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1] - 'a'): -1; |
| 35 | } |
| 36 | |
| 37 | // Sort the suffixes using the comparison function |
| 38 | // defined above. |
| 39 | sort(suffixes, suffixes+n, cmp); |
| 40 | |
| 41 | // At his point, all suffixes are sorted according to first |
| 42 | // 2 characters. Let us sort suffixes according to first 4 |
| 43 | // characters, then first 8 and so on |
| 44 | int ind[n]; // This array is needed to get the index in suffixes[] |
| 45 | // from original index. This mapping is needed to get |
| 46 | // next suffix. |
| 47 | for (int k = 4; k < 2*n; k = k*2) |
| 48 | { |
| 49 | // Assigning rank and index values to first suffix |
| 50 | int rank = 0; |
| 51 | int prev_rank = suffixes[0].rank[0]; |
| 52 | suffixes[0].rank[0] = rank; |
| 53 | ind[suffixes[0].index] = 0; |
| 54 | |
| 55 | // Assigning rank to suffixes |
| 56 | for (int i = 1; i < n; i++) |
| 57 | { |
| 58 | // If first rank and next ranks are same as that of previous |
| 59 | // suffix in array, assign the same new rank to this suffix |
| 60 | if (suffixes[i].rank[0] == prev_rank && |
| 61 | suffixes[i].rank[1] == suffixes[i-1].rank[1]) |
| 62 | { |
| 63 | prev_rank = suffixes[i].rank[0]; |
| 64 | suffixes[i].rank[0] = rank; |
| 65 | } |
| 66 | else // Otherwise increment rank and assign |
| 67 | { |
| 68 | prev_rank = suffixes[i].rank[0]; |
| 69 | suffixes[i].rank[0] = ++rank; |
| 70 | } |
| 71 | ind[suffixes[i].index] = i; |
| 72 | } |
| 73 | |
| 74 | // Assign next rank to every suffix |
| 75 | for (int i = 0; i < n; i++) |
| 76 | { |
| 77 | int nextindex = suffixes[i].index + k/2; |
| 78 | suffixes[i].rank[1] = (nextindex < n)? |
| 79 | suffixes[ind[nextindex]].rank[0]: -1; |