BNUOJ 34990 Justice String

Justice String

Time Limit: 2000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld Java class name: Main

Given 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

3
aaabcd
abee
aaaaaa
aaaaa
aaaaaa
aabbb

Sample Output

Case #1: 2
Case #2: 0
Case #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 long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 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
",cs++,ans);
75     }
76     return 0;
77 }

View Code