首页 > 代码库 > BNUOJ 34990 Justice String
BNUOJ 34990 Justice String
Justice String
Time Limit: 2000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: MainGiven two strings A and B, your task is to find a substring of A called justice string, which has the same length as B, and only has at most two characters different from B.
Input
The first line of the input contains a single integer T, which is the number of test cases.
For each test case, the first line is string A, and the second is string B.
Both string A and B contain lowercase English letters from a to z only. And the length of these two strings is between 1 and 100000, inclusive.
Output
For each case, first output the case number as "Case #x: ", and x is the case number. Then output a number indicating the start position of substring C in A, position is counted from 0. If there is no such substring C, output -1.
And if there are multiple solutions, output the smallest one.
Sample Input
3aaabcdabeeaaaaaaaaaaaaaaaaaaabbb
Sample Output
Case #1: 2Case #2: 0Case #3: -1
Source
2014 ACM-ICPC Beijing Invitational Programming Contest
解题：Hash+二分
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 100100;18 char sa[maxn],sb[maxn];19 unsigned LL Ha[maxn],Hb[maxn],p = 131;20 int len1,len2;21 unsigned LL pp[maxn];22 int calc(int a,int b){23 int high = min(len1 - a,len2 - b),low = 0,mid,ans = 0;24 while(low <= high){25 mid = (low + high)>>1;26 unsigned LL v1 = Ha[a] - Ha[a+mid]*pp[mid];27 unsigned LL v2 = Hb[b] - Hb[b+mid]*pp[mid];28 if(v1 == v2){29 ans = mid;30 low = mid + 1;31 }else high = mid - 1;32 }33 return ans;34 }35 int main() {36 int T,cs = 1;37 pp[0] = 1;38 for(int i = 1; i < maxn; ++i) pp[i] = pp[i-1]*p;39 scanf("%d",&T);40 while(T--){41 scanf("%s %s",sa,sb);42 len1 = strlen(sa);43 len2 = strlen(sb);44 Ha[len1] = 0;45 Hb[len2] = 0;46 for(int i = len1-1; i >= 0; --i) Ha[i] = Ha[i+1]*p + sa[i];47 for(int i = len2-1; i >= 0; --i) Hb[i] = Hb[i+1]*p + sb[i];48 int ans = -1;49 for(int i = 0; i <= len1 - len2; ++i){50 int sum = 0,a = i,b = 0,tmp = 0;51 tmp = calc(a,b);52 if(tmp >= len2-2){53 ans = i;54 break;55 }56 sum += tmp;57 a += tmp+1;58 b += tmp+1;59 tmp = calc(a,b);60 sum += tmp;61 if(sum >= len2-2){62 ans = i;63 break;64 }65 a += tmp+1;66 b += tmp+1;67 tmp = calc(a,b);68 sum += tmp;69 if(sum >= len2-2){70 ans = i;71 break;72 }73 }74 printf("Case #%d: %d\n",cs++,ans);75 }76 return 0;77 }
BNUOJ 34990 Justice String
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。