后缀数组
从给定的字符串中，我们可以获得所有可能的后缀。在按字典顺序对后缀进行排序之后，我们可以获得后缀数组。后缀数组也可以使用后缀树来形成。通过使用后缀树的DFS遍历，我们可以获得后缀数组。后缀数组有助于找到线性时间的后缀。我们还可以通过使用二进制搜索类型过程使用后缀数组查找子字符串。
时间复杂度为O（mlogn）
输入输出
Input: Main String: “BANANA”, Pattern: “NAN” Output: Pattern found at position: 2
算法
fillSuffixArray（文本，suffArray）
输入： 主字符串
输出： 后缀数组
Begin
n := text Length
define suffix array as allSuffix of size n
for i := 0 to n-1, do
allSuffix[i].index := i
allSuffix[i].suff := substring of text from (i to end)
done
sort the allSuffix array
store indexes of all suffix array in suffArray.
EndsuffixArraySearch（文本，模式，suffArray）
输入：主字符串，模式和后缀数组
输出-找到样式的位置
Begin
patLen := size of pattern
strLen := size of text
left := 0
right := strLen -1
while left <= right, do
mid := left + (right - left)/2
tempStr := substring of text from suffArray[mid] to end
result := compare tempStr and pattern upto pattern length.
if result = 0, then
print the location
if res < 0, then
right := mid – 1
else
left := mid +1
done
End示例
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct suffix {
int index;
string suff;
};
int strCompare(string st1, string st2, int n) {
int i = 0;
while(n--) {
if(st1[i] != st2[i])
return st1[i] - st2[i];
i++;
}
return 0;
}
bool comp(suffix suff1, suffix suff2) { //compare two strings for sorting
if(suff1.suff<suff2.suff)
return true;
return false;
}
void fillSuffixArray(string mainString, int suffArr[]) {
int n = mainString.size();
suffix allSuffix[n]; //array to hold all suffixes
for(int i = 0; i<n; i++) {
allSuffix[i].index = i;
allSuffix[i].suff = mainString.substr(i); //from ith position to end
}
sort(allSuffix, allSuffix+n, comp);
for(int i = 0; i<n; i++)
suffArr[i] = allSuffix[i].index; //indexes of all sorted suffix
}
void suffixArraySearch(string mainString, string pattern, int suffArr[], int array[], int *index) {
int patLen = pattern.size();
int strLen = mainString.size();
int left = 0, right = strLen - 1; //left and right for binary search
while(left <= right) {
int mid = left + (right - left)/2;
string tempStr = mainString.substr(suffArr[mid]);
int result = strCompare(pattern,tempStr, patLen);
if(result == 0) { //the pattern is found
(*index)++;
array[(*index)] = suffArr[mid];
}
if(result < 0)
right = mid -1;
else
left = mid +1;
}
}
int main() {
string mainString = "BANANA";
string pattern = "NAN";
int locArray[mainString.size()];
int index = -1;
int suffArr[mainString.size()];
fillSuffixArray(mainString, suffArr);
suffixArraySearch(mainString, pattern, suffArr, locArray, &index);
for(int i = 0; i <= index; i++) {
cout << "Pattern found at position: " << locArray[i]<<endl;
}
}输出结果
Pattern found at position: 2