4 条题解
-
0
[NOIP2020] 字符串匹配
#include <bits/stdc++.h> using namespace std; const int MAXN = (1 << 20); int n; string s; int z[MAXN + 5]; void exKMP(const string &s) { z[0] = 0; for (int l = 0, r = 0, i = 1; i < s.length(); i++) { // s[i...r] == s[i-l...r-l] if (i <= r && z[i - l] < r - i + 1) z[i] = z[i - l]; else { z[i] = max(0, r - i + 1); while (i + z[i] < s.length() && s[z[i]] == s[i + z[i]]) z[i]++; } if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } } // s[0..i] 出现了奇数次的字符的个数 int cnt[MAXN + 5]; // s[i..n-1] 出现了奇数次的字符的个数 int tnc[MAXN + 5]; int temp[30]; void getCntTnc(const string &s) { int len = s.length(); memset(temp, 0, sizeof(temp)); cnt[0] = 1; temp[s[0] - 'a']++; for (int i = 1; i < len; i++) { cnt[i] = cnt[i - 1]; int now = s[i] - 'a'; temp[now]++; if (temp[now] % 2 == 0) cnt[i]--; else cnt[i]++; } memset(temp, 0, sizeof(temp)); tnc[len - 1] = 1; temp[s[len - 1] - 'a']++; for (int i = len - 2; i >= 0; i--) { tnc[i] = tnc[i + 1]; int now = s[i] - 'a'; temp[now]++; if (temp[now] % 2 == 0) tnc[i]--; else tnc[i]++; } } //树状数组 long long tr[30]; int lowbit(int x) { return x & (-x); } void add(int x) { for (int i = x; i <= 27; i += lowbit(i)) tr[i]++; } long long query(int x) { long long res = 0; for (int i = x; i >= 1; i -= lowbit(i)) res += tr[i]; return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; while (n--) { cin >> s; int len = s.length(); exKMP(s); getCntTnc(s); /* cout << "--------------\n"; for (int i = 0; i < s.length(); i++) cout << z[i] << " "; cout << "\n"; for (int i = 0; i < s.length(); i++) cout << cnt[i] << " "; cout << "\n"; for (int i = 0; i < s.length(); i++) cout << tnc[i] << " "; cout << "\n"; */ memset(tr, 0, sizeof(tr)); long long ans = 0; //枚举循环节长度 cLen for (int cLen = 2; cLen <= len - 1; cLen++) { add(cnt[cLen - 2] + 1); //循环节的最多循环次数 cK int cK = z[cLen] / cLen + 1; if (cLen * cK == len) cK--; int cKE = cK / 2; //偶数的循环次数情况数 int cKO = cK - cKE; //奇数的循环次数情况数 //(AB)^{cKE}C // cnt[i] <= tnc[0] : for i in range(cLen) ans += query(tnc[0] + 1) * cKE; //(AB)^{cKO}C // cnt[i] <= tnc[cLen] ans += query(tnc[cLen] + 1) * cKO; // cout << cLen << ":" << query(tnc[0]) << "," << cKE << " " << query(tnc[cLen]) << " " << cKO << endl; } cout << ans << "\n"; } return 0; } -
0
33DAI LV 5 (1/1) @ 2023-3-30 20:58:06
P4824 [USACO15FEB] Censoring S
#include <bits/stdc++.h> using namespace std; const int MAXN = 2000000; int nxt[MAXN + 5]; int main() { ios::sync_with_stdio(false); cin.tie(0); string s, t; string ans; //t+#+s cin >> s >> t; //初始化t+"#", s是占位使用的 ans = t + "#" + s; nxt[0] = 0; for (int i = 1; i < t.length() + 1; i++) { int j = nxt[i - 1]; while (j > 0 && ans[j] != ans[i]) j = nxt[j - 1]; if (ans[j] == ans[i]) j++; nxt[i] = j; } //把s逐个放进来 int i = 0; //把s[i] int j = t.length() + 1; //放入ans[j] while (i < s.length()) { ans[j] = s[i]; i++; int k = nxt[j - 1]; while (k > 0 && ans[k] != ans[j]) k = nxt[k - 1]; if (ans[k] == ans[j]) k++; nxt[j] = k; if (nxt[j] < t.length()) j++; else j = j - t.length() + 1; } for (int i = t.length() + 1; i < j; i++) cout << ans[i]; return 0; } -
0
扩展KMP/Z函数
#include <bits/stdc++.h> using namespace std; const int MAXLEN = 20000000; // a, b长度的最大值 string a, b; int aLen, bLen; // 把s的z函数数组求出来 int z[MAXLEN + 5]; void getZ(const string &s) { int l, r; // s[l]~s[r] 与 s 开头 r-l+1 个字符相同 l = -1, r = -1; z[0] = 0; for (int i = 1; i < s.length(); i++) { z[i] = 0; if (l <= i && i <= r) // s[0]~s[r-l] == s[l]~s[r] // s[i-l] == s[i] // s[i-l]~s[r-l] == s[i]~s[r] // z[i-l]: s[i-l] 开始的 z[i-l] 这么多个字符和开头的这么多个字符相同 z[i] = min(z[i - l], r - i + 1); // i开始已有 z[i] 长度与开头相等 // 如果 i 开始的第 z[i]+1 个位置 // 与开头开始的第 z[i]+1 个位置相等z[i]就可以多一个长度 while (i + z[i] < s.length() && z[i] < s.length() && s[i + z[i]] == s[0 + z[i]]) z[i]++; // s[i] 开始的 z[i] 个字符，与开头的 z[i] 个字符相等 // s[i]~s[i+z[i]-1] if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } z[0] = s.length(); } // b 与 a 的每一个后缀的 LCP 长度数组 zz。 int zz[MAXLEN + 5]; void getZZ(const string &a, const string &b) { // z[i] : b[0]~ 与 b[i]~ 的 lcp getZ(b); // zz[i] : b[0]~ 与 a[i]~ 的 lcp int l, r; // b[0] ~ b[r-l] == a[l] ~ a[r] l = -1, r = -1; for (int i = 0; i < a.length(); i++) { zz[i] = 0; if (l <= i && i <= r) // b[0]~s[r-l] == a[l]~a[r] // b[i-l] == a[i] // 1: b[i-l]~s[r-l] == a[i]~a[r] // 2: b[i-l] 开始的 z[i-l] 个字符与 b 开头的 z[i - l] 个字符相等 // 由 1,2 可得 zz[i] 可以以 z[i-l] 作为基础 zz[i] = min(z[i - l], r - i + 1); // a[i] 开始已有 zz[i] 长度与 b 开头相等 // 如果 a[i] 开始的第 zz[i]+1 个位置 // 与 b[0] 开始的第 zz[i]+1 个位置相等 // 那么 z[i]就可以多一个长度 while (i + zz[i] < a.length() && zz[i] < b.length() && a[i + zz[i]] == b[0 + zz[i]]) zz[i]++; // s[i] 开始的 z[i] 个字符，与开头的 z[i] 个字符相等 // s[i]~s[i+z[i]-1] if (i + zz[i] - 1 > r) l = i, r = i + zz[i] - 1; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> a >> b; aLen = a.length(); bLen = b.length(); getZZ(a, b); long long ans; ans = 0; for (long long i = 0; i <= bLen - 1; i++) ans = ans ^ ((i + 1) * (z[i] + 1)); cout << ans << "\n"; ans = 0; for (long long i = 0; i <= aLen - 1; i++) ans = ans ^ ((i + 1) * (zz[i] + 1)); cout << ans << "\n"; return 0; } -
0
动物园
#include <bits/stdc++.h> #define int long long using namespace std; const int MOD = 1000000007; int T; string s; int ans; int cnt[1123456]; //不考虑重叠限制的数量 int nxt[1123456]; void gen_nxt(const string &t) { nxt[0] = 0; cnt[0] = 1; for (int i = 1; i < t.length(); i++) { int j = nxt[i - 1]; while (j && t[i] != t[j]) j = nxt[j - 1]; if (t[i] == t[j]) j++; nxt[i] = j; if (j > 0) cnt[i] = cnt[j - 1] + 1; else cnt[i] = 1; } } int get_ans(const string &t) { int ans = 1; for (int i = 1, j = 0; i < t.length(); i++) { while (j && t[i] != t[j]) j = nxt[j - 1]; if (t[i] == t[j]) j++; while (j && j * 2 > i + 1) j = nxt[j - 1]; ans = (ans * (cnt[j - 1] + 1)) % MOD; } return ans; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> T; while (T--) { cin >> s; gen_nxt(s); cout << get_ans(s) << "\n"; } return 0; }
- 1