【hdu 6208】The Dominator of Strings
The of HDU strings
2023-09-14 09:03:49 时间
【链接】h在这里写链接
【题意】
问你n个串里面有没有一个串,使得其余n-1个串都是他的子串。
【题解】
后缀数组.
答案肯定是那个最长的串。
则,把那个串求一下Sa数组(注意仅仅那个最长的串求)。
然后枚举其余n-1个子串。
看看它们是不是那个最长的串的子串;
(可以用一个类似二分的东西判断它是不是子串。);
(字符串比较,如果比当前后缀小,就往后缀小的地方,否则往大的地方,最后判断是不是子串。)
->利用Sa数组。
时间复杂度为O(n*logn)的样子。
感觉又解锁了新姿势。
(这里可以不用获取Height函数了)
【错的次数】
0
【反思】
主串的长度没那么长的时候,用这种方法的确合适。
hdu 2222那题。主串的长度太长了(1e6);
就显得没那么优秀了。
【代码】
#include<bits/stdc++.h> using namespace std; const int N = 1e5; const int SN = 2e2; const int MAX_CHAR = 300;//每个数字的最大值。 int s[N + 10];//如果是数字,就写成int s[N+10]就好,从0开始存 int Sa[N + 10], T1[N + 10], T2[N + 10], C[N + 10], T; int Height[N + 10], Rank[N + 10], idx[N + 10], in[N + 10], tag, L[N + 10], R[N + 10]; int Le[N + 10]; vector <string> vec; bool flag[N + 10]; void build_Sa(int n, int m) { int i, *x = T1, *y = T2; for (i = 0; i<m; i++) C[i] = 0; for (i = 0; i<n; i++) C[x[i] = s[i]]++; for (i = 1; i<m; i++) C[i] += C[i - 1]; for (i = n - 1; i >= 0; i--) Sa[--C[x[i]]] = i; for (int k = 1; k <= n; k <<= 1) { int p = 0; for (i = n - k; i<n; i++) y[p++] = i; for (i = 0; i<n; i++) if (Sa[i] >= k) y[p++] = Sa[i] - k; for (i = 0; i<m; i++) C[i] = 0; for (i = 0; i<n; i++) C[x[y[i]]]++; for (i = 1; i<m; i++) C[i] += C[i - 1]; for (i = n - 1; i >= 0; i--) Sa[--C[x[y[i]]]] = y[i]; swap(x, y); p = 1; x[Sa[0]] = 0; for (i = 1; i<n; i++) x[Sa[i]] = y[Sa[i - 1]] == y[Sa[i]] && y[Sa[i - 1] + k] == y[Sa[i] + k] ? p - 1 : p++; if (p >= n) break; m = p; } } bool contain(string &S, string T) {//最长的那个串和 短串 int l = 1, r = S.size(),temp = -1; while (l <= r) { int m = (l + r) >> 1; if (S.compare(Sa[m], T.length(), T) <= 0)//如果后缀比S来的小。 { temp = m; l = m + 1;//可以再大一点 } else { r = m - 1; } } if (temp == -1) return 0; else return S.compare(Sa[temp], T.length(), T) == 0; } int main() { //freopen("F:\\rush.txt", "r", stdin); ios::sync_with_stdio(0), cin.tie(0); int TT; cin >> TT; while (TT--) { int T; cin >> T; int n = 0, ma = 0, idxma; string ss; vec.clear(); vec.push_back(" "); for (int i = 1; i <= T; i++) { cin >> ss; vec.push_back(ss); if ((int)ss.size() > ma) { ma = (int)ss.size(); idxma = i; } } for (int i = 0; i <= (int) vec[idxma].size() - 1; i++) s[n++] = vec[idxma][i]; s[n] = 0; build_Sa(n + 1, MAX_CHAR);//注意调用n+1 bool ok = true; for (int i = 1; i <= T; i++) if (idxma!=i){//不能是最大的那个,那个是要被匹配的。 if (!contain(vec[idxma], vec[i])) { ok = false; break; } } if (ok) { cout << vec[idxma] << endl; } else cout << "No" << endl; } return 0; }
相关文章
- ORA-01378: The logical block size (string) of file string is not compatible with the disk sector size (media sector size is string and host sector size is string) ORACLE 报错 故障修复 远程处理
- ORA-46014: The value of the “aclFile” element is too long. ORACLE 报错 故障修复 远程处理
- ORA-48929: The trace record size exceeded the max size that can be read [string] ORACLE 报错 故障修复 远程处理
- ORA-02762: file number to be cancelled is greater than the maximum. ORACLE 报错 故障修复 远程处理
- ORA-09981: skxfqdreg: Error Adding a page to the SDI buffer pool ORACLE 报错 故障修复 远程处理
- ORA-16736: unable to find the destination entry of standby database “string” in V$ARCHIVE_DEST ORACLE 报错 故障修复 远程处理
- ORA-16810: multiple errors or warnings detected for the database ORACLE 报错 故障修复 远程处理
- MySQL 5.7.17:The Latest Upgrade of the Database System(mysql5.7.17)
- Unveiling the Power of RARP Linux(rarplinux)
- Exploring the Dynamic Duo: The Power of Solr MongoDB Integration(solrmongodb)
- Unlocking the Power of Data: How to Use AVG in MySQL to Analyze Information Like a Pro(avgmysql)
- Exploring the Benefits of Linux Hub for Streamlined Networking(linuxhub)
- 如何使用Redis查看键的过期时间?How to use Redis to view the expiration time of a key?(redis查看过期时间)
- Exploring the versatility of Linux: The significance of the var directory(linux系统var)
- Revolutionizing the OS World: Launching the Latest Version of Linux(launchlinux)
- Discover the Versatility of Tilda Linux: The Perfect Operating System for Tech Enthusiasts.(tildalinux)
- Discover the Power of Linux with YLMF: The UserFriendly Operating System(linuxylmf)
- Exploring the Versatility of Linux UDP Transfer: Tips and Tricks for Efficient Data Transfer(linuxudp传输)
- Exploring the Power of MySQL and C for Advanced Database Management(mysqlcpp)
- Exploring the Benefits of MySQL Crossdatabase querying(mysql跨库联查)
- Exploring the Versatile World of Linux PDA: Features Applications and Advantages(linuxpda)