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)。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) cerr << "Line : " << (x) << " >>>>>>\n";
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef map<LL, int> MPS;
typedef pair<int, int> PII;
typedef MPS::iterator IT; const int maxn = + ;
const int B = (int)1e6 + ; char sa[maxn], sb[maxn];
ULL pw[maxn], ha[maxn], hb[maxn];
int n, m, k;
void pre(){
pw[] = ;
for(int i = ; i < maxn; i++)
pw[i] = pw[i-]*B;
}
inline ULL cal(ULL h[], int l, int r, int len){
return h[l]-h[r+]*pw[len];
}
inline int idx(char ch){
return ch - 'a';
}
int main() { pre();
while(scanf("%s%s%d", sa, sb, &k) == ){
n = strlen(sa);
m = strlen(sb);
ha[n] = hb[m] = ;
for(int i = n-; i >= ; i--)
ha[i] = ha[i+]*B+idx(sa[i]);
for(int i = m-; i >= ; i--)
hb[i] = hb[i+]*B+idx(sb[i]);
int ans = ;
for(int i = ; i <= n-m; i++){
int j = , x = ;
// bug(i)
while(x <= k && j < m){
while(j < m && sa[i+j] != sb[j] && x <= k)
j++, x++;
// bug(j)
if(j >= m || x > k) break;
int l = j, r = m;
while(l+ < r){
int mid = (l+r)>>;
// bug(mid)
ULL h1 = cal(ha, i+l, i+mid, mid-l+);
ULL h2 = cal(hb, l, mid, mid-l+);
if(h1 == h2)
l = mid;
else r = mid;
}
if(l != m-)
x++;
j = l+;
}
ans += x <= k;
}
printf("%d\n", ans);
}
return ;
}
北京邀请赛同样的分析方法。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) cerr << "Line : " << (x) << " >>>>>>\n";
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef map<LL, int> MPS;
typedef pair<int, int> PII;
typedef MPS::iterator IT; const int maxn = + ;
const int B = (int)1e6 + ; char sa[maxn], sb[maxn];
ULL pw[maxn], ha[maxn], hb[maxn];
int n, m, k;
void pre() {
pw[] = ;
for(int i = ; i < maxn; i++)
pw[i] = pw[i-]*B;
}
inline ULL cal(ULL h[], int l, int r, int len) {
return h[l]-h[r+]*pw[len];
}
inline int idx(char ch) {
return ch - 'a';
}
int main() { pre();
int T;
for(int t = scanf("%d", &T); t <= T; t++) {
k = ;
scanf("%s%s", sa, sb);
n = strlen(sa);
m = strlen(sb);
ha[n] = hb[m] = ;
for(int i = n-; i >= ; i--)
ha[i] = ha[i+]*B+idx(sa[i]);
for(int i = m-; i >= ; i--)
hb[i] = hb[i+]*B+idx(sb[i]);
int ans = -;
for(int i = ; i <= n-m; i++) {
int j = , x = ;
// bug(i)
while(x <= k && j < m) {
while(j < m && sa[i+j] != sb[j] && x <= k)
j++, x++;
// bug(j)
if(j >= m || x > k) break;
int l = j, r = m;
while(l+ < r) {
int mid = (l+r)>>;
// bug(mid)
ULL h1 = cal(ha, i+l, i+mid, mid-l+);
ULL h2 = cal(hb, l, mid, mid-l+);
if(h1 == h2)
l = mid;
else r = mid;
}
if(l != m-)
x++;
j = l+;
}
if(x <= k) {
ans = i;
break;
}
}
printf("Case #%d: %d\n", t, ans);
}
return ;
}