百度怎么把自己网站展现在百度,杭州黑马程序员培训机构怎么样,同企网站建设做网站,手机网站备案欢迎关注更多精彩 关注我#xff0c;学习常用算法与数据结构#xff0c;一题多解#xff0c;降维打击。
基本问题
给定一个字符串s, 返回一个数组Z, Z[i]代表子串s[i…n] 与s最长公共前缀的长度。
朴素做法
可以枚举所有s[i…n]子串#xff0c;然后与s一一比较#x…欢迎关注更多精彩 关注我学习常用算法与数据结构一题多解降维打击。
基本问题
给定一个字符串s, 返回一个数组Z, Z[i]代表子串s[i…n] 与s最长公共前缀的长度。
朴素做法
可以枚举所有s[i…n]子串然后与s一一比较复杂度O(n*n)
优化
可以参照KMP的思想利用已经判断过的相同串。 利用该思想可以将复杂度缩小到O(n) vectorint Zfunc(string str) {int n str.size();vectorintz(n);int l 0, r 0;for (int i 1; i n; i) {if (i r) {z[i] min(r - i 1, z[i - l]);}// 循环只有在i z[i]r时才会运算。总运算次数为n次。while (i z[i] n str[z[i]] str[i z[i]]) {z[i];}if (i z[i] - 1 r) {l i;r i z[i] - 1;}}return z;
}
题目一
https://codeforces.com/contest/1968/problem/G1
题目大意
给定一个字符串s和数字k问将字符串分成连续k段公共前缀最长是多少。
题目分析
可以通过二分枚举长度l然后查找s[0…l]在s中出现的次数利用公共前缀数组实现每次判断为O(n), 整体复杂度为nlog(n)。
代码
#include iostream
#include stdio.h
#include queue
#include string.h
#include stack
#include vector
#include map
#include algorithm
#include assert.husing namespace std;typedef long long lld;vectorint Zfunc(string str) {int n str.size();vectorintz(n);int l 0, r 0;for (int i 1; i n; i) {if (i r) {z[i] min(r - i 1, z[i - l]);}while (i z[i] n str[z[i]] str[i z[i]]) {z[i];}if (i z[i] - 1 r) {l i;r i z[i] - 1;}}return z;
}int getCnt(vectorint Z, int len) {int cnt 1;for (int i len; i Z.size();) {if (Z[i] len) {cnt;i len;}else i;}return cnt;
}void solve() {int t;cin t;while (t--) {int n, l, r;cin n l r;string s;cin s;auto Z Zfunc(s);/*for (int z : Z)cout z ;cout endl;*/int left 0, right s.length() / l;while (left right) {int mid (left right) / 2 (left right) % 2;if (getCnt(Z, mid) r) {left mid;}else {right mid - 1;}}cout left endl;}
}int main() {solve();return 0;
}
/*
7
3 3 3
aba
3 3 3
aaa
7 2 2
abacaba
9 4 4
abababcab
10 1 1
codeforces
9 3 3
abafababa
5 3 3
zpozp2
10 1 1
aaaaaaaaaa
10 1 1
abcdaabcda*/
题目二
https://codeforces.com/contest/1968/problem/G2
题目大意
该题是上一题的加强版本。 给定一个字符串s和数字l,r问将字符串分成连续k段(kl,l1,l2,…,r)公共前缀最长是多少。
题目分析
先求出k1到s.length()的所有答案用数组ans表示。 可以分段考虑对于ksqrt(n), 可以按照题目一的做法总复杂度为sqrt(n) n log(n) 对于ksqrt(n), 那么分段后的长度不会大于sqrt(n), 可以枚举l 从1到sqrt(n) 计算出最多可以分成多少段k则ans[k]l。 保险起见最后做一遍最大值比较ans[i-1]max(ans[i-1], ans[i])。
代码 #include iostream
#include stdio.h
#include queue
#include string.h
#include stack
#include vector
#include map
#include algorithm
#include cmathusing namespace std;typedef long long lld;vectorint Zfunc(string str) {int n str.size();vectorintz(n);int l 0, r 0;for (int i 1; i n; i) {if (i r) {z[i] min(r - i 1, z[i - l]);}while (i z[i] n str[z[i]] str[i z[i]]) {z[i];}if (i z[i] - 1 r) {l i;r i z[i] - 1;}}return z;
}int getCnt(vectorint Z, int len) {int cnt 1;for (int i len; i Z.size();) {if (Z[i] len) {cnt;i len;}else i;}return cnt;
}int getFix(vectorint Z, string s, int k) {int left 0, right s.length() / k;while (left right) {int mid (left right) / 2 (left right) % 2;if (getCnt(Z, mid) k) {left mid;}else {right mid - 1;}}return left;
}void solve() {int t;cin t;while (t--) {int n, l, r;cin n l r;string s;cin s;auto Z Zfunc(s);vectorint ans(s.length() 1, 0);int sl sqrt(s.length()) 0.5;for (int i 1; i sl; i) {ans[i] max(ans[i], getFix(Z, s, i));int k getCnt(Z, i);ans[k] max(ans[k], i);}for (int i s.length()-1; i 0; --i) {ans[i] max(ans[i 1], ans[i]);}for (; l r; l) {cout ans[l] ;}cout endl;}
}int main() {solve();return 0;
}
/*
7
3 3 3
aba
3 3 3
aaa
7 2 2
abacaba
9 4 4
abababcab
10 1 1
codeforces
9 3 3
abafababa
5 3 3
zpozp2
10 1 1
aaaaaaaaaa
10 1 1
abcdaabcda7
3 1 3
aba
3 2 3
aaa
7 1 5
abacaba
9 1 6
abababcab
10 1 10
aaaaaaawac
9 1 9
abafababa
7 2 7
vvzvvvv*/ 本人码农希望通过自己的分享让大家更容易学懂计算机知识。创作不易帮忙点击公众号的链接。
