字符串基础
[NOIP 2018 普及组] 字符统计
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> int main() { std::string s; std::getline(std::cin, s); int cnt = 0; for (char c : s) if (c != ' ' and c != '\n') cnt ++; std::cout << cnt << '\n'; } |
[NOIP 2011 普及组] 统计单词数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <bits/stdc++.h> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); std::string s, t; std::cin >> t; std::getline(std::cin, s); std::getline(std::cin, s); for (auto &c : t) { if ('A' <= c and c <= 'Z') c = c - 'A' + 'a'; } for (auto &c : s) { if ('A' <= c and c <= 'Z') c = c - 'A' + 'a'; } int cnt = 0, fist = -1; for (int i = 0, j = 0; i < s.size(); i = j) { while (j < s.size() and 'a' <= s[j] and s[j] <= 'z') ++ j; if (j == i) { ++ j; continue; } if (j - i != t.size()) continue; bool flag = true; for (int k = i; k < j and flag; ++ k) if (s[k] != t[k - i]) flag = false; if (not flag) continue; if (not cnt) fist = i; cnt ++; } if (cnt) std::cout << cnt << ' ' << fist << '\n'; else std::cout << -1 << '\n'; } |
数字反转
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <bits/stdc++.h> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); std::string s; std::cin >> s; int dot = -1; int line = -1; int per = -1; for (int i = 0; i < s.size(); ++ i) { if (s[i] == '.') dot = i; else if (s[i] == '/') line = i; else if (s[i] == '%') per = i; } if (dot != -1) { std::string a = s.substr(0, dot); std::string b = s.substr(dot + 1); while (a.size() > 1 and a.back() == '0') a.pop_back(); std::reverse(a.begin(), a.end()); std::reverse(b.begin(), b.end()); while (b.size() > 1 and b.back() == '0') b.pop_back(); std::cout << a << '.' << b << '\n'; } else if (line != -1) { std::string a = s.substr(0, line); std::string b = s.substr(line + 1); while (a.size() > 1 and a.back() == '0') a.pop_back(); while (b.size() > 1 and b.back() == '0') b.pop_back(); std::reverse(a.begin(), a.end()); std::reverse(b.begin(), b.end()); std::cout << a << '/' << b << '\n'; } else if (per != -1) { s.pop_back(); while (s.size() > 1 and s.back() == '0') s.pop_back(); std::reverse(s.begin(), s.end()); std::cout << s << "%\n"; } else { while (s.size() > 1 and s.back() == '0') s.pop_back(); std::reverse(s.begin(), s.end()); std::cout << s << '\n'; } } |
CF 1935 A. Entertainment in MAC
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; string s; cin >> s; string ss = s; reverse(ss.begin(), ss.end()); if (n & 1) { if (s <= ss) { cout << s << ss; } else { cout << ss; } } else { if (s <= ss) { cout << s; } else { cout << ss << s; } } cout << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) solve(); } |
CF 1941 C. Rudolf and the Ugly String
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <bits/stdc++.h> using namespace std; void solve() { vector<string> template_s { "mapie", "map", "pie" }; int n; string s; cin >> n >> s; int res = 0; for (int i = 0; i < n; ++ i) { for (auto &t : template_s) { if (s.substr(i, t.size()) == t) { res ++; i += t.size() - 1; break; } } } cout << res << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) solve(); } |
字符串哈希
给出一种类STL的哈希实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
constexpr int N = 110; constexpr int mod = 97; template<typename Key, typename Val, int N> struct hash_map { int idx; std::array<int, N> h, ne; std::array<Key, N> key; std::array<Val, N> val; std::function<int(const Key&)> Hash; std::function<bool(const Key&, const Key&)> equal; hash_map(std::function<int(const Key&)> _Hash, std::function<bool(const Key&, const Key&)> _equal) : Hash(_Hash), equal(_equal) { h.fill(0); idx = 0; } Val find(const Key &k) { int pos = Hash(k); for (int i = h[pos]; i; i = ne[i]) { if (equal(key[i], k)) return val[i]; } return Val(); } void insert(const Key &k, const Val &v) { int pos = Hash(k); for (int i = h[pos]; i; i = ne[i]) { if (equal(key[i], k)) { val[i] = v; return; } } key[++ idx] = k; val[idx] = v; ne[idx] = h[pos]; h[pos] = idx; } Val& operator[](const Key &k) { int pos = Hash(k); for (int i = h[pos]; i; i = ne[i]) { if (equal(key[i], k)) return val[i]; } ++ idx; ne[idx] = h[pos]; h[pos] = idx; key[idx] = k; return val[idx]; } }; |
[JLOI 2011] 不重复数字
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <bits/stdc++.h> void solve() { int n; std::cin >> n; std::unordered_map<int, bool> hash_map; for (int i = 1; i <= n; ++ i) { int x; std::cin >> x; if (not hash_map[x]) std::cout << x << ' '; hash_map[x] = true; } std::cout << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
Snowflake Snow Snowflakes
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include <iostream> #include <cstring> #include <cstdio> #define SNOW_SIZE 6 typedef long long LL; const int N = 1e6 + 10; const int P = 1000003; int snow[N][6]; int h[N], ne[N], idx; int is_prime(int x) { for (int i = 2; i <= x / i; ++ i) if (x % i == 0) return false; return true; } void find_pre_prime(int N) { int p = N; while (not is_prime(p)) -- p; std::cout << p << '\n'; } int hash(int *snowflake) { LL a = 0, b = 1; for (int i = 0; i < SNOW_SIZE; ++ i) { a = (a + snowflake[i]) % P; b = b * snowflake[i] % P; } a = (a + (LL)snowflake[0] * snowflake[3] % P) % P; a = (a + (LL)snowflake[1] * snowflake[4] % P) % P; a = (a + (LL)snowflake[2] * snowflake[5] % P) % P; return (a + b) % P; } bool equal(int *a, int *b) { for (int i = 0; i < SNOW_SIZE; ++ i) { bool flag = true; for (int j = 0; j < SNOW_SIZE and flag; ++ j) { if (a[(i + j) % SNOW_SIZE] != b[j]) flag = false; } if (flag) return true; flag = true; for (int j = 0; j < SNOW_SIZE and flag; ++ j) { if (a[(i + j) % SNOW_SIZE] != b[SNOW_SIZE - 1 - j]) flag = false; } if (flag) return true; } return false; } bool insert(int *a) { int val = hash(a); for (int i = h[val]; i; i = ne[i]) { if (equal(snow[i], a)) return true; } memcpy(snow[++ idx], a, sizeof(int) * SNOW_SIZE); ne[idx] = h[val]; h[val] = idx; return false; } int main() { // find_pre_prime(N); int n; scanf("%d", &n); for (int i = 1; i <= n; ++ i) { int a[10]; for (int j = 0; j < SNOW_SIZE; ++ j) scanf("%d", a + j); if (insert(a)) { printf("Twin snowflakes found.\n"); return 0; } } printf("No two snowflakes are alike.\n"); } |
【模板】字符串哈希
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <bits/stdc++.h> using LL = long long; using PII = std::pair<int, int>; constexpr int N = 10000 + 10; constexpr int base = 131; constexpr int mod1 = 1e9 + 7; constexpr int mod2 = 1e9 + 9; PII a[N]; int Hash(std::string &s, int mod) { LL res = 0; for (auto &c : s) { res = res * base % mod; res = (res + c) % mod; } return res; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int n; std::cin >> n; for (int i = 1; i <= n; ++ i) { std::string s; std::cin >> s; a[i] = {Hash(s, mod1), Hash(s, mod2)}; } std::sort(a + 1, a + 1 + n); // for (int i = 1; i <= n; ++ i) // std::cout << a[i].first << ' ' << a[i].second << std::endl; int cnt = 1; for (int i = 2; i <= n; ++ i) if (a[i] != a[i - 1]) cnt ++; std::cout << cnt << '\n'; } |
字符串匹配
伪代码
|
1 2 3 4 5 6 |
get string s, t let n=s.size(), m=t.size() let ans=0 for i=1 to n: if Hash(s[i:i+m])==Hash(t): ans+=1 |
最长回文子串
$O(nlogn)$ 做法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
#include <iostream> #include <cstring> #include <cstdio> typedef long long LL; const int N = 1000000 + 10; const int maxn = 30 * N; const int base = 131; const int mod1 = 1e9 + 7; // 双模数 const int mod2 = 1e9 + 9; char s[N]; inline int momo(int x, int mod) { return (x % mod + mod) % mod; } inline void chkmax(int &a, const int &b) { if (a < b) a = b; } struct strhash { int b[N], h[N], mod; int rh[N]; strhash(int mod) : mod(mod) { b[0] = 1; for (int i = 1; i < N; ++ i) b[i] = (LL)b[i - 1] * base % mod; } void init(char *s, int n) { h[0] = 0; // 正向哈希 for (int i = 1; i <= n; ++ i) { h[i] = (LL)h[i - 1] * base % mod; h[i] = ((LL)h[i] + s[i]) % mod; } rh[n + 1] = 0; // 反向哈希 for (int i = n; i; -- i) { rh[i] = (LL)rh[i + 1] * base % mod; rh[i] = ((LL)rh[i] + s[i]) % mod; } } int get(int l, int r) { return momo(h[r] - (LL)h[l - 1] * b[r - l + 1] % mod, mod); } int rget(int l, int r) { return momo(rh[l] - (LL)rh[r + 1] * b[r - l + 1] % mod, mod); } bool check(int l, int r) { // 判断是否为回文 return get(l, r) == rget(l, r); } } h1(mod1), h2(mod2); bool check_odd(int R, int n, int pos) { // 此时圆心刚好位于回文中心字符 // pos 刚好表示字符位置 int l = pos - R; int r = pos + R; if (0 < l && l <= r && r <= n) { return h1.check(l, r) && h2.check(l, r); } return false; } bool check_even(int R, int n, int pos) { // 此时圆心夹在中心字符之间 // pos 表示圆心位于[pos,pos+1]字符之间 int l = pos - R + 1; int r = pos + R; if (0 < l && l < r && r <= n) { return h1.check(l, r) && h2.check(l, r); } return false; } int solve() { int n = strlen(s + 1); h1.init(s, n); h2.init(s, n); int res = 1; // 最长奇数回文串 for (int i = 1; i <= n; ++ i) { // 二分回文半径 // 此处的回文半径定义为回文串长度除以2下取整 int l = 0, r = n / 2 + 1; while (l < r) { int mid = l + r + 1 >> 1; if (check_odd(mid, n, i)) l = mid; else r = mid - 1; } chkmax(res, 2 * l + 1); } // 最长偶数回文串 for (int i = 1; i < n; ++ i) { int l = 1, r = n / 2 + 1; while (l < r) { int mid = l + r + 1 >> 1; if (check_even(mid, n, i)) l = mid; else r = mid - 1; } chkmax(res, 2 * l); } return res; } bool is_end() { return s[1] == 'E' && s[2] == 'N' && s[3] == 'D'; } int main() { int T = 0; while (~scanf("%s", s + 1)) { if (is_end()) break; printf("Case %d: %d\n", ++ T, solve()); } } |
$O(n)$ 做法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
int solve() { int n = strlen(s + 1); if (n == 1) return 1; h1.init(s, n); h2.init(s, n); R[1] = 1; R[2] = s[1] == s[2] ? 2 : 1; for (int i = 3; i <= n; ++ i) { R[i] = 1; for (int j = std::min(R[i - 1] + 2, i); j; -- j) { int l = i - j + 1; int r = i; if (h1.check(l, r) && h2.check(l, r)) { R[i] = j; break; } } } int res = 1; for (int i = 1; i <= n; ++ i) { chkmax(res, R[i]); } return res; } |
最长公共子串
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include <bits/stdc++.h> using ULL = unsigned long long; constexpr int N = 1e6 + 10; int power[N]; ULL base = 131; struct strhash { std::vector<ULL> hash, rhash; int n; strhash() = default; strhash(const std::string &s) : n(s.size() - 1), hash(s.size()), rhash(s.size()) { hash[0] = 0; for (int i = 1; i <= n; i++) { hash[i] = hash[i - 1] * base + s[i]; } rhash[n] = 0; for (int i = n - 1; i >= 1; i--) { rhash[i] = rhash[i + 1] * base + s[i]; } } ULL get(int l, int r) { return hash[r] - hash[l - 1] * power[r - l + 1]; } ULL rget(int l, int r) { return rhash[l] - rhash[r + 1] * power[r - l + 1]; } bool check(int l, int r) { return get(l, r) == rget(l, r); } }; int main() { power[0] = 1; for (int i = 1; i < N; i++) { power[i] = power[i - 1] * base; } int n, m; std::cin >> n >> m; std::vector<std::string> s(1); std::vector<strhash> h(1); int maxlen = 0; for (int i = 1; i <= n; ++ i) { std::string str; std::cin >> str; maxlen = std::max(maxlen, (int)str.size()); str = " " + str; s.push_back(str); h.emplace_back(str); } ULL anshash = 0; auto check = [&](int x) -> bool { std::vector<std::set<ULL>> hash(n + 1); for (int i = 1; i <= n; ++ i) { for (int j = 1; j + x - 1 < (int)s[i].size(); ++ j) { hash[i].insert(h[i].get(j, j + x - 1)); } } std::set<ULL> &union_set = hash[1]; for (int i = 2; i <= n; ++ i) { std::set<ULL> tmp; std::set_intersection(union_set.begin(), union_set.end(), hash[i].begin(), hash[i].end(), std::inserter(tmp, tmp.begin())); union_set = tmp; } if (!union_set.empty()) { anshash = *union_set.begin(); return true; } return false; }; int l = 0, r = maxlen; while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) { l = mid; } else { r = mid - 1; } } std::cout << l << '\n'; auto find_ans = [&](ULL hash) -> std::string { for (int i = 1; i <= n; ++ i) { for (int j = 1; j + l - 1 < (int)s[i].size(); ++ j) { if (h[i].get(j, j + l - 1) == hash) { return s[i].substr(j, l); } } } return ""; }; std::cout << find_ans(anshash) << '\n'; } |
智乃的前缀、后缀、回文
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <bits/stdc++.h> using namespace std; constexpr int N = 1e5 + 10; bool pre[N], suf[N]; void calc(string &s, int n, bool *pre) { vector<int> d1(n); for (int i = 0, l = 0, r = -1; i < n; i++) { int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1); while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) { k++; } d1[i] = k--; if (i + k > r) { l = i - k; r = i + k; } } vector<int> d2(n); for (int i = 0, l = 0, r = -1; i < n; i++) { int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1); while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) { k++; } d2[i] = k--; if (i + k > r) { l = i - k - 1; r = i + k; } } for (int i = 0; i < n; ++ i) { int l = i - d1[i] + 1, r = i + d1[i] - 1; if (!l && !pre[r]) pre[r] = true; l = i - d2[i], r = i + d2[i] - 1; if (!l && !pre[r]) pre[r] = true; } } int main() { cin.tie(0)->sync_with_stdio(0); int n, m; string s, t; cin >> n >> m >> s >> t; if (n > m) swap(s, t), swap(n, m); calc(s, n, suf); reverse(s.begin(), s.end()); calc(s, n, pre); int pre_same = -1; for (int i = 0; i < n; ++ i) { if (s[i] != t[i]) break; pre_same = i; } int suf_same = n; for (int i = 0; i < n; ++ i) { if (s[n - 1 - i] != t[m - 1 - i]) break; suf_same = n - i - 1; } vector<int> L, R; for (int i = 0; i < n; ++ i) { int j = n - 1 - i; if (pre[i] && i <= pre_same) L.push_back(i); if (suf[j] && i >= suf_same) R.push_back(i); } int ans = -1; for (auto left: L) { auto it = upper_bound(R.begin(), R.end(), left); if (it != R.end()) { int right = *it; if (left < right) { ans = max(ans, n - right + left + 1); } } } if (~ans) ans <<= 1; cout << ans << '\n'; } |
前缀函数和KMP算法
【模板】KMP
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <bits/stdc++.h> void KMP(std::string &s, std::string &t) { int n = s.size() - 1, m = t.size() - 1; std::vector<int> next(m + 1, 0); for (int i = 2, j = 0; i <= m; ++ i) { while (j && t[i] != t[j + 1]) j = next[j]; if (t[i] == t[j + 1]) ++j; next[i] = j; } for (int i = 1, j = 0; i <= n; ++ i) { while (j && s[i] != t[j + 1]) j = next[j]; if (s[i] == t[j + 1]) ++j; if (j == m) { std::cout << i - m + 1 << std::endl; j = next[j]; } } for (int i = 1; i <= m; ++ i) std::cout << next[i] << " "; std::cout << std::endl; } int main() { std::string s, t; std::cin >> s >> t; s = " " + s; t = " " + t; KMP(s, t); } |
字符串的周期
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <stdio.h> const int N = 1e6 + 10; char s[N]; int n, next[N]; void solve(char *s, int n) { next[1] = 0; for (int i = 2, j = 0; i <= n; ++ i) { while (j && s[j + 1] != s[i]) j = next[j]; if (s[j + 1] == s[i]) j ++; next[i] = j; } for (int i = 2; i <= n; ++ i) { if (next[i] && i % (i - next[i]) == 0) { printf("%d %d\n", i, i / (i - next[i])); } } puts(""); } int main() { int T = 0; while (~scanf("%d", &n) && n) { scanf("%s", s + 1); printf("Test case #%d\n", ++ T); solve(s, n); } } |
最小表示法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <bits/stdc++.h> std::string Minimum_representation(std::string &s) { int n = s.size(); s = " " + s + s; int i = 1, j = 2, k; while (i <= n && j <= n) { for (k = 0; k <= n && s[i + k] == s[j + k]; ++ k); if (k == n) break; if (s[i + k] > s[j + k]) { i += k + 1; if (i == j) ++ i; } else { j += k + 1; if (i == j) ++ j; } } return s.substr(std::min(i, j), n); } int main() { std::cin.tie(0)->sync_with_stdio(0); std::string s, t; std::cin >> s >> t; s = Minimum_representation(s); t = Minimum_representation(t); if (s == t) { std::cout << "Yes\n" << s << '\n'; } else { std::cout << "No\n"; } } |
本质不同的子串数量
$O(n^2)$ 做法，前缀函数。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <bits/stdc++.h> // 本来打算写下标从1开始的写法 // 结果被 copliot 教学了一下下标从0开始的写法 // 这下被完爆了 std::vector<int> calc_next(std::string &s) { int n = s.size(); std::vector<int> next(n); for (int i = 1, j = 0; i < n; ++ i) { while (j > 0 && s[i] != s[j]) j = next[j - 1]; if (s[i] == s[j]) ++ j; next[i] = j; } return next; } int The_number_of_intrinsically_different_substrings(std::string &s) { std::string t; int ans = 0; for (char c : s) { t = c + t; auto next = calc_next(t); ans += t.size() - *std::max_element(next.begin(), next.end()); } return ans; } int main() { std::cin.tie(0)->sync_with_stdio(0); std::string s; std::cin >> s; std::cout << The_number_of_intrinsically_different_substrings(s) << '\n'; } |
汗流浃背了，这个是 copilot 给出的 $O(nlog(n)log(n))$ 做法（然而实际上我并算不来这个复杂度，但是至少这个算法本地可以跑 $n=10^5$）。我被 AI 完爆了，我是说。我还没看懂这个算法，真的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <bits/stdc++.h> int The_number_of_intrinsically_different_substrings(std::string &s) { int n = s.size(); std::vector<int> sa(n), rk(n), height(n); for (int i = 0; i < n; ++ i) { sa[i] = i; rk[i] = s[i]; } for (int w = 1; w < n; w <<= 1) { auto cmp = [&](int i, int j) { return rk[i] == rk[j] ? rk[i + w] < rk[j + w] : rk[i] < rk[j]; }; std::sort(sa.begin(), sa.end(), cmp); std::vector<int> tmp(n); for (int i = 1; i < n; ++ i) { tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]); } for (int i = 0; i < n; ++ i) { rk[i] = tmp[i]; } } for (int i = 0, k = 0; i < n; ++ i) { if (rk[i] == 0) { k = 0; continue; } if (k) -- k; int j = sa[rk[i] - 1]; while (i + k < n && j + k < n && s[i + k] == s[j + k]) ++ k; height[rk[i]] = k; } int res = n - sa[0]; for (int i = 1; i < n; ++ i) { res += n - sa[i] - height[i]; } return res; } int main() { std::cin.tie(0)->sync_with_stdio(0); std::string s; std::cin >> s; std::cout << The_number_of_intrinsically_different_substrings(s) << '\n'; } |
发表回复