赞
踩
这道题是我在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]; else return 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; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。