首页 > 代码库 > hihocoder 1084 扩展KMP && 2014 北京邀请赛 Justice String

hihocoder 1084 扩展KMP && 2014 北京邀请赛 Justice String

2024-08-09 12:18:23   218人阅读

hihocoder 1084 : http://hihocoder.com/problemset/problem/1084

北京邀请赛 Just  String http://www.bnuoj.com/v3/problem_show.php?pid=34990

两道题同样的做法，题目基本内容是找到A的字串中和B串长度一样，且不同的字符个数不超过k个的置。

以hihocoder 1084为例， 是求有多少个A的字串的，与B串长度一样，且不同的字符个数不超过k。

分析：预处理hash，然后对每个字串进行判断，例如A[i~i+len-1] 和B[0~len-1], 首先找到一个A，B都相同的字符，然后从此出发找到长度尽可能大的完全相同的一截，这里可以用二分完成，然后再次找到一个对应位置A，B相同的字符，一旦不相同的字符个数超过k则立马终止，这样复杂度接近O(N*logN*k)。

代码：

技术分享
 1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 #define esp 1e-14 5 #define lson   l, m, rt<<1 6 #define rson   m+1, r, rt<<1|1 7 #define sz(x) ((int)((x).size())) 8 #define pf(x) ((x)*(x)) 9 #define pb push_back10 #define pi acos(-1.0)11 #define in freopen("solve_in.txt", "r", stdin);12 #define bug(x) cerr << "Line : " << (x) <<  " >>>>>>\n";13 #define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;14 #define inf 0x0f0f0f0f15 16 using namespace std;17 typedef long long LL;18 typedef unsigned long long ULL;19 typedef map<LL, int> MPS;20 typedef pair<int, int> PII;21 typedef MPS::iterator IT;22 23 const int maxn = 100000 + 100;24 const int B = (int)1e6 + 9;25 26 char sa[maxn], sb[maxn];27 ULL pw[maxn], ha[maxn], hb[maxn];28 int n, m, k;29 void pre(){30     pw[0] = 1;31     for(int i = 1; i < maxn; i++)32         pw[i] = pw[i-1]*B;33 }34 inline ULL cal(ULL h[], int l, int r, int len){35     return h[l]-h[r+1]*pw[len];36 }37 inline int idx(char ch){38     return ch - ‘a‘;39 }40 int main() {41     42     pre();43     while(scanf("%s%s%d", sa, sb, &k) == 3){44         n = strlen(sa);45         m = strlen(sb);46         ha[n] = hb[m] = 0;47         for(int i = n-1; i >= 0; i--)48             ha[i] = ha[i+1]*B+idx(sa[i]);49         for(int i = m-1; i >= 0; i--)50             hb[i] = hb[i+1]*B+idx(sb[i]);51         int ans = 0;52         for(int i = 0; i <= n-m; i++){53             int j = 0, x = 0;54 //            bug(i)55             while(x <= k && j < m){56                 while(j < m && sa[i+j] != sb[j] && x <= k)57                     j++, x++;58 //                bug(j)59                 if(j >= m || x > k) break;60                 int l = j, r = m;61                 while(l+1 < r){62                     int mid = (l+r)>>1;63 //                    bug(mid)64                     ULL h1 = cal(ha, i+l, i+mid, mid-l+1);65                     ULL h2 = cal(hb, l, mid, mid-l+1);66                     if(h1 == h2)67                         l = mid;68                     else r = mid;69                 }70                 if(l != m-1)71                 x++;72                 j = l+2;73             }74             ans += x <= k;75         }76         printf("%d\n", ans);77     }78     return 0;79 }
View Code

 

北京邀请赛同样的分析方法。

代码：

技术分享
 1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 #define esp 1e-14 5 #define lson   l, m, rt<<1 6 #define rson   m+1, r, rt<<1|1 7 #define sz(x) ((int)((x).size())) 8 #define pf(x) ((x)*(x)) 9 #define pb push_back10 #define pi acos(-1.0)11 #define in freopen("solve_in.txt", "r", stdin);12 #define bug(x) cerr << "Line : " << (x) <<  " >>>>>>\n";13 #define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;14 #define inf 0x0f0f0f0f15 16 using namespace std;17 typedef long long LL;18 typedef unsigned long long ULL;19 typedef map<LL, int> MPS;20 typedef pair<int, int> PII;21 typedef MPS::iterator IT;22 23 const int maxn = 100000 + 100;24 const int B = (int)1e6 + 9;25 26 char sa[maxn], sb[maxn];27 ULL pw[maxn], ha[maxn], hb[maxn];28 int n, m, k;29 void pre() {30     pw[0] = 1;31     for(int i = 1; i < maxn; i++)32         pw[i] = pw[i-1]*B;33 }34 inline ULL cal(ULL h[], int l, int r, int len) {35     return h[l]-h[r+1]*pw[len];36 }37 inline int idx(char ch) {38     return ch - ‘a‘;39 }40 int main() {41 42     pre();43     int T;44     for(int t = scanf("%d", &T); t <= T; t++) {45         k = 2;46         scanf("%s%s", sa, sb);47         n = strlen(sa);48         m = strlen(sb);49         ha[n] = hb[m] = 0;50         for(int i = n-1; i >= 0; i--)51             ha[i] = ha[i+1]*B+idx(sa[i]);52         for(int i = m-1; i >= 0; i--)53             hb[i] = hb[i+1]*B+idx(sb[i]);54         int ans = -1;55         for(int i = 0; i <= n-m; i++) {56             int j = 0, x = 0;57 //            bug(i)58             while(x <= k && j < m) {59                 while(j < m && sa[i+j] != sb[j] && x <= k)60                     j++, x++;61 //                bug(j)62                 if(j >= m || x > k) break;63                 int l = j, r = m;64                 while(l+1 < r) {65                     int mid = (l+r)>>1;66 //                    bug(mid)67                     ULL h1 = cal(ha, i+l, i+mid, mid-l+1);68                     ULL h2 = cal(hb, l, mid, mid-l+1);69                     if(h1 == h2)70                         l = mid;71                     else r = mid;72                 }73                 if(l != m-1)74                     x++;75                 j = l+2;76             }77             if(x <= k) {78                 ans = i;79                 break;80             }81         }82         printf("Case #%d: %d\n", t, ans);83     }84     return 0;85 }
View Code

 

hihocoder 1084 扩展KMP && 2014 北京邀请赛 Justice String


联系
我们