BNUOJ34990--Justice String （exkmp求最长公共前缀）

Justice String

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

题意：两个字符串， 求B在在A串出现的第一个位置， 可以允许最多两个字符不同。
做法： 依次枚举位置i， 然后求A[i, ...lena - 1]与B的最长公共前缀， 再求 A[i, i+lenb-1]的B的最长公共后缀。。 然后对于中间那一部分， 用多项式hash直接判断是否相等。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int seed = 1e9+7;
  4 const int MAXN = 1e5+10;
  5 typedef unsigned long long uLL;
  6 uLL _hash[2][MAXN];
  7 string s1, s2;
  8 void Hash(string s, int d){
  9     int len = s.size();
 10     memset(_hash[d], 0, sizeof (_hash[d]));
 11     for (int i = 0; i < len; i++){
 12         _hash[d][i] = (i ? _hash[d][i-1] : 0) * seed + s[i] - '0';
 13     }
 14 }
 15 void pre_kmp(string &s, int m, int next[]){
 16     next[0] = m;
 17     int j = 0;
 18     while (j + 1 < m && s[j] == s[j+1]){
 19         j++;
 20     }
 21     next[1] = j;
 22     int k = 1;
 23     for (int i = 2; i < m; i++){
 24         int p = next[k] + k - 1;
 25         int L = next[i-k];
 26         if (i + L < p + 1){
 27             next[i] = L;
 28         }else{
 29             j = max(0, p-i+1);
 30             while (i+j < m && s[i+j] == s[j]){
 31                 j++;
 32             }
 33             next[i] = j;
 34             k = i;
 35         }
 36     }
 37 }
 38 void exkmp(string &str1, int len1, string &str2, int len2, int next[], int extend[]){
 39     pre_kmp(str1, len1, next);
 40     int j = 0;
 41     while (j < len2 && j < len1 && str1[j] == str2[j]){
 42         j++;
 43     }
 44     extend[0] = j;
 45     int k = 0;
 46     for (int i = 1; i < len2; i++){
 47         int p = extend[k] + k - 1;
 48         int L = next[i-k];
 49         if (i + L < p + 1){
 50             extend[i] = L;
 51         }else{
 52             j = max(0, p-i+1);
 53 
 54             while (i+j < len2 && j < len1 && str2[i+j] == str1[j]){
 55                 j++;
 56             }
 57             extend[i] = j;
 58             k = i;
 59         }
 60     }
 61 }
 62 int ex1[MAXN], ex2[MAXN], next[MAXN];
 63 uLL bas[MAXN];
 64 void pre_solve(){
 65     bas[0] = 1;
 66     for (int i = 1; i < MAXN; i++){
 67         bas[i] = bas[i-1] * seed;
 68     }
 69 }
 70 int main(){
 71 
 72     //freopen("in.txt", "r", stdin);
 73     pre_solve();
 74     int T, cas = 1;
 75     scanf ("%d", &T);
 76     while (T--){
 77         cin >> s1 >> s2;
 78         int len1 = s1.size();
 79         int len2 = s2.size();
 80         Hash(s1, 0);
 81         Hash(s2, 1);
 82         string tmp1 = s1;
 83         string tmp2 = s2;
 84         reverse(tmp1.begin(), tmp1.end());
 85         reverse(tmp2.begin(), tmp2.end());
 86         exkmp(s2, len2, s1, len1, next, ex1);
 87         exkmp(tmp2, len2, tmp1, len1, next, ex2);
 88         int ans = -1;
 89         for (int i = 0; i < len1; i++){
 90             int t1 = ex1[i];
 91             int t2 = ex2[len1 - i - len2];
 92             int L1 = i+t1, R1 = i+len2-t2-1;
 93             int L2 = t1, R2 = len2-t2-1;
 94             bool ok1 = ((t1 == len2) || (R1 <= L1+1));
 95 
 96             uLL p1 = (_hash[0][R1-1] - _hash[0][L1] * bas[R1-1-L1]);
 97             uLL p2 = (_hash[1][R2-1] - _hash[1][L2] * bas[R2-1-L2]);
 98             bool ok2 = (p1 == p2);
 99             if (ok1 || ok2){
100                 ans = i;
101                 break;
102             }
103         }
104         printf("Case #%d: %d
", cas++, ans);
105     }
106     return 0;
107 }