计算不同的非空子串

计算方法

这道题是我在BCSP-X小高组的题目中发现的一道

没事闲的就写了代码和思路：

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>using namespace std;// 用于存储后缀数组的比较函数
struct Suffix {int index;int rank[2];
};// 比较函数
int cmp(struct Suffix a, struct Suffix b) {if (a.rank[0] == b.rank[0])return a.rank[1] < b.rank[1];elsereturn a.rank[0] < b.rank[0];
}// 构建后缀数组
vector<int> buildSuffixArray(string s) {int n = s.size();struct Suffix suffixes[n];for (int i = 0; i < n; i++) {suffixes[i].index = i;suffixes[i].rank[0] = s[i] - 'a';suffixes[i].rank[1] = (i + 1 < n) ? (s[i + 1] - 'a') : -1;}sort(suffixes, suffixes + n, cmp);int ind[n];for (int k = 4; k < 2 * n; k = k * 2) {int rank = 0;int prev_rank = suffixes[0].rank[0];suffixes[0].rank[0] = rank;ind[suffixes[0].index] = 0;for (int i = 1; i < n; i++) {if (suffixes[i].rank[0] == prev_rank && suffixes[i].rank[1] == suffixes[i - 1].rank[1]) {prev_rank = suffixes[i].rank[0];suffixes[i].rank[0] = rank;} else {prev_rank = suffixes[i].rank[0];suffixes[i].rank[0] = ++rank;}ind[suffixes[i].index] = i;}for (int i = 0; i < n; i++) {int nextIndex = suffixes[i].index + k / 2;suffixes[i].rank[1] = (nextIndex < n) ? suffixes[ind[nextIndex]].rank[0] : -1;}sort(suffixes, suffixes + n, cmp);}vector<int> suffixArr(n);for (int i = 0; i < n; i++)suffixArr[i] = suffixes[i].index;return suffixArr;
}// 构建LCP数组
vector<int> buildLCPArray(string s, vector<int> suffixArr) {int n = s.size();vector<int> lcp(n, 0);vector<int> invSuffix(n, 0);for (int i = 0; i < n; i++)invSuffix[suffixArr[i]] = i;int k = 0;for (int i = 0; i < n; i++) {if (invSuffix[i] == n - 1) {k = 0;continue;}int j = suffixArr[invSuffix[i] + 1];while (i + k < n && j + k < n && s[i + k] == s[j + k])k++;lcp[invSuffix[i]] = k;if (k > 0)k--;}return lcp;
}// 计算不同非空子串的数量
int countUniqueSubstrings(string s) {int n = s.size();vector<int> suffixArr = buildSuffixArray(s);vector<int> lcp = buildLCPArray(s, suffixArr);int totalSubstrings = n * (n + 1) / 2;int lcpSum = 0;for (int i = 0; i < n; i++)lcpSum += lcp[i];return totalSubstrings - lcpSum;
}// 主函数
int main() {string s;cin >> s;cout << "不同非空子串的数量: " << countUniqueSubstrings(s) << endl;return 0;
}