查看原题请戳这里
首先，这道题让求最大值最小，于是我们就很自然得想到了去二分这个最小值。
那么，怎么check呢？
我们发现，如果直接暴力去check，即二分区间长度+暴力枚举字符串+暴力枚举区间左端点+暴力对比，那么时间复杂度是$O(n^2m^2\log_2n)$的。（引人深思的复杂度……）
很显然，我们需要去优化这个时间复杂度。
首先，如果我们对要进行对比的区间进行哈希，然后用set进行判断，就可以将时间复杂度降低到$O(nm^2\log_2^2n)$。
这里提供两种用set去检验的思路：
- 用一个set去记录好的基因有多少不同的哈希值$cnt1$，再用一个set去记录坏的基因有多少不同的哈希值$cnt2$，再用一个set去记录好的基因和坏的基因一共有多少不同的哈希值$cnt3$，如果$cnt3-cnt1=cnt2$，那么好的基因的哈希值和坏的基因的哈希值没有重复。
- 用一个set去储存好的基因的哈希值，然后用set自带的find函数查询每一个坏的基因的哈希值是否在这个集合中出现过。
但是，即便如此，我们的时间复杂度依然无法通过这道题，主要原因是每次记录哈希值都占用了大量的时间。
$hash[i]-hash[j-1]\times pri^{i-j+1}(i>j)$快速求得$hash[i][j]$的值。
时间复杂度：$O(nm\log_2 n)$
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
#define ll long long
#define INF 0x7fffffff
#define re register
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define qwq printf("qwq\n");
#define mod1 122420729
#define mod2 131937371
using namespace std;
int read()
{
register int x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
int n,m,l,r,mid,cnt1,cnt2,cnt3;
long long hfg[505][505],hfb[505][505],a[505],b[505],c[505];
char good[505][505],bad[505][505];
void Hash()
{
memset(hfg,0,sizeof(hfg));
memset(hfb,0,sizeof(hfb));
for(register int i = 0; i < n; i++) hfg[i][0] = good[i][0];
for(register int i = 0; i < n; i++) hfb[i][0] = bad[i][0];
for(register int i = 0; i < n; i++)
for(register int j = 1; j < m; j++)
hfg[i][j] = hfg[i][j - 1] * 13331 + good[i][j];
for(register int i = 0; i < n; i++)
for(register int j = 1; j < m; j++)
hfb[i][j] = hfb[i][j - 1] * 13331 + bad[i][j];
}
void get_Hash(int s,int l)
{
if(s == 0)
{
for(int i = 0; i < n; i++) a[i] = hfg[i][l - 1];
for(int i = 0; i < n; i++) b[i] = hfb[i][l - 1];
return ;
}
for(int i = 0; i < n; i++) a[i] = hfg[i][s + l - 1] - hfg[i][s - 1] * c[l];
for(int i = 0; i < n; i++) b[i] = hfb[i][s + l - 1] - hfb[i][s - 1] * c[l];
}
set<int> se1,se2,se3;
bool check(int l)
{
for(register int i = 0; i + l - 1 < m; i++)
{
get_Hash(i,l);
int flag = 1;
se1.clear(); se2.clear(); se3.clear();
for(register int j = 0; j < n; j++) se1.insert(a[j]),se3.insert(a[j]);
cnt1 = se1.size();
for(register int j = 0; j < n; j++) se2.insert(b[j]),se3.insert(b[j]);
cnt2 = se2.size();
if(se3.size() - cnt1 == cnt2) return true;
}
return false;
}
int main()
{
n = read(); m = read();
c[1] = 13331;
for(int i = 2; i <= m; i++) c[i] = c[i - 1] * 13331;
for(register int i = 0; i < n; i++) cin >> good[i];
for(register int i = 0; i < n; i++) cin >> bad[i];
l = 1; r = m;
Hash();
while(l < r)
{
mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
get_Hash(1,4);
printf("%d\n",r);
return 0;
}
|
