SYZOJP186 你猜猜是不是DP 二分+hash解法
SYZOJP186 你猜猜是不是DP题解
题目传送门
现在给两个仅包含小写字母的字符串a,b ，求a 与b的最长公共连续子串的长度。
对于20%的数据，a,b长度 ∈ [1, 200]
对于50%的数据，a,b长度 ∈ [1, 20000]
对于100%的数据, a,b长度 ∈ [1, 200000]
分析
根据数据规模，DP肯定是要GG的
应该是要用比较神奇的字符串算法，但是本题猪油一组测试数据，经过计算，发现二分答案+hash函数可以通过。
做法
- 此题可以二分答案长度len
- 计算两个字符串各个起点长度为len的子串hash得两hash数组A,B。并从大到小排序。
- 两个指针p,q分别指向A,B数组。从前往后扫描。
- 如果p,q所指元素hash相等。
a. A数组中所有hash值和p所指元素相同的元素构成的集合为AA。
b. 同理有集合BB。
c. AA和BB的集合都需要两两检验是否有相同子串。
d. 有则标记跳出。
e. 若都无，p,q后移。 - 不相等，则hash值大者后移。
- 如果p,q所指元素hash相等。
复杂度
排序
<nobr aria-hidden="true"> O(Llog2L) </nobr> <math display="block" xmlns="http://www.w3.org/1998/Math/MathML"> <mi> O </mi> <mo stretchy="false"> ( </mo> <mi> L </mi> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi> log </mi> <mrow class="MJX-TeXAtom-ORD"> <mn> 2 </mn> </mrow> </msub> <mi> L </mi> </mrow> <mo stretchy="false"> ) </mo> </math>
总的期望
<nobr aria-hidden="true"> O(Llog22L) </nobr> <math display="block" xmlns="http://www.w3.org/1998/Math/MathML"> <mi> O </mi> <mo stretchy="false"> ( </mo> <mi> L </mi> <mrow class="MJX-TeXAtom-ORD"> <msubsup> <mi> log </mi> <mrow class="MJX-TeXAtom-ORD"> <mn> 2 </mn> </mrow> <mn> 2 </mn> </msubsup> <mi> L </mi> </mrow> <mo stretchy="false"> ) </mo> </math>
貌似如果AA集合和BB集合都含有大量元素，规模相当于 <nobr aria-hidden="true"> O(L) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> O </mi> <mo stretchy="false"> ( </mo> <mi> L </mi> <mo stretchy="false"> ) </mo> </math> ，且实际上每个字串优势不想等的则复杂度就 <nobr aria-hidden="true"> O(L2log2L) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> O </mi> <mo stretchy="false"> ( </mo> <msup> <mi> L </mi> <mn> 2 </mn> </msup> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi> log </mi> <mrow class="MJX-TeXAtom-ORD"> <mn> 2 </mn> </mrow> </msub> <mi> L </mi> </mrow> <mo stretchy="false"> ) </mo> </math>
但这种出现的概率应当是 比中五百万彩票还要小
以此 <nobr aria-hidden="true"> O(Llog22L) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> O </mi> <mo stretchy="false"> ( </mo> <mi> L </mi> <mrow class="MJX-TeXAtom-ORD"> <msubsup> <mi> log </mi> <mrow class="MJX-TeXAtom-ORD"> <mn> 2 </mn> </mrow> <mn> 2 </mn> </msubsup> <mi> L </mi> </mrow> <mo stretchy="false"> ) </mo> </math> 再与 <nobr aria-hidden="true"> 108 </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <msup> <mn> 10 </mn> <mn> 8 </mn> </msup> </math> 相比得0.35左右。故应当可以AC
/* 653 ms 6500 K C++ / 2.1 K */
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
void hash(string &s,ULL h[],ULL g[],ULL C)
{
h[s.length()]=0;
for (int i=s.length()-1;i>=0;--i)
h[i]=h[i+1]*C+s[i];
g[0]=1;
for (size_t i=1;i<=s.length();++i)
g[i]=g[i-1]*C;
}
ULL sub_hash(int i,int j,ULL h[],ULL g[])//[i,j)
{
return h[i]-h[j]*g[j-i];
}
const int maxl=200005;
string a,b;
ULL ga[maxl],ha[maxl],gb[maxl],hb[maxl];
ULL C=131;
struct nd{
ULL h;
int i;
}A[maxl],B[maxl];
bool operator <(nd a,nd b)
{
return a.h>b.h;
}
int main()
{
int ans,l,r,m,len,la,lb,ka,kb;
cin>>a>>b;
hash(a,ha,ga,C);
hash(b,hb,gb,C);
la=a.length(); lb=b.length();
l=0; r=min(la,lb)+1;
//ans is in [l,r)
while (l+1<r) {
len=m=(l+r+1)/2;
ka=la-len+1; kb=lb-len+1;
for (int i=0;i<ka;++i) {
A[i].i=i;
A[i].h=sub_hash(i,i+len,ha,ga);
}
for (int i=0;i<kb;++i) {
B[i].i=i;
B[i].h=sub_hash(i,i+len,hb,gb);
}
sort(A,A+ka);
sort(B,B+kb);
bool ok=false;
int p=0,q=0;
int same_ar,same_br;
int u,v;
while (!ok&&p<ka&&q<kb) {
if (A[p].h==B[q].h) {
for (same_ar=p+1;same_ar<ka;++same_ar) if (A[p].h!=A[same_ar].h) break;
for (same_br=q+1;same_br<kb;++same_br) if (B[q].h!=B[same_br].h) break;
for (u=p;!ok&&u<same_ar;u++)
for (v=q;v<same_br;v++)
if (a.substr(A[u].i,len)==b.substr(B[v].i,len)) {
ok=true;break;
}
p=same_ar;q=same_br;
} else if (A[p].h>B[q].h) {
++p;
} else {
++q;
}
}
if (ok) {
l=m;
} else {
r=m;
}
}
ans=l;
cout<<ans<<endl;
}
