T1
这是一道 manacher 模板，但是我们使用 二分 + hash \(O(n \log n)\) 的做法。
显然地，若长为 \(len\) 的回文串存在，则长为 \(len-2,len-4,...\) 的回文串也一定存在（在两端各删去若干相同字符即可）。
至此，我们发现回文串分两类：奇回文串、偶回文串，在每一类当中分别具有单调性。
于是我们对于同一对称轴，进行两遍二分，check 用 hash 判回文即可。
奇、偶回文串对于答案的贡献即为 \(l \times 2\) 和 \(l \times 2 + 1\)。
于是我们得到了 24 pts。
code
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
using namespace std;
const int N=1e7+5;
const int BASE=13331;
int n,ans=-1e9;
string s,t;
ull hs[N],ht[N],p[N];
void init_hash(){
p[0]=1;
for(int i=1;i<=n;i++) p[i]=p[i-1]*BASE;
for(int i=1;i<=n;i++) hs[i]=hs[i-1]*BASE+s[i];
for(int i=n;i>=1;i--) ht[i]=ht[i+1]*BASE+s[i];
}
int get_hs(int l,int r){
return hs[r]-hs[l-1]*p[r-l+1];
}
int get_ht(int l,int r){
return ht[l]-ht[r+1]*p[r-l+1];
}
signed main(){
cin>>s,n=s.size(),s='#'+s;
init_hash();
for(int i=1;i<=n;i++){
int l=0,r=min(i-1,n-i+1)+1;
while(l+1<r){
int mid=(l+r)>>1;
if(get_hs(i-mid,i-1)==get_ht(i,i+mid-1)) l=mid;
else r=mid;
}
ans=max(ans,l*2);
l=0,r=min(i-1,n-i)+1;
while(l+1<r){
int mid=(l+r)>>1;
if(get_hs(i-mid,i-1)==get_ht(i+1,i+mid)) l=mid;
else r=mid;
}
ans=max(ans,l*2+1);
}
cout<<ans;
return 0;
}
T2/T3
很妙的一道题阿。
我们钦定含通配符的字符串为 \(S\)，文件名列表里的当前字符串为 \(T\)。
我们注意到询问仅关心是否匹配上了,考虑 dp。
我们又发现通配符个数 \(\le 10\)，考虑按通配符划分状态。
令 \(dp_{i,j}\) 表示 \(S\) 以第 \(i\) 个通配符结尾，\(T\) 以第 \(j\) 个字符结尾时是否能匹配上。
初始状态：\(dp_{0,0}=1\)，答案：判断 \(dp_{tot,\mid T \mid}\)（\(tot\) 表示 \(S\) 中通配符个数，\(|T|\) 表示 \(T\) 的长度）。
转移：
-
若当前通配符为 *
若 \(dp_{i,j-1}=1\)，则 \(dp_{i,j}=1\)（不停往下扩展，因为 * 可以包含任意个字符）
-
否则
枚举与之匹配的 \(T\) 中的与其长度相同的子串，用 hash 检测是否相同，
-
若下一个通配符为 ?
\(dp_{i+1,j+len+1} = 1\)（延长一个也可匹配成功）
-
否则
\(dp_{i+1,j+len}=1\)
-
一些细节见代码。
code
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=15;
const int BASE=13331;
int n;
ull hs[N],ht[N],p[N];
bool dp[M][N];
string s;
vector<int> pos;
void init_hash(){
p[0]=1;
for(int i=1;i<=N;i++) p[i]=p[i-1]*BASE;
for(int i=1;i<s.size();i++) hs[i]=hs[i-1]*BASE+s[i];
}
ull get_hs(int l,int r){
return hs[r]-hs[l-1]*p[r-l+1];
}
ull get_ht(int l,int r){
return ht[r]-ht[l-1]*p[r-l+1];
}
string sol(string t){
memset(dp,0,sizeof(dp)),dp[0][0]=1;
t='#'+t+'#';
for(int i=1;i<t.size();i++) ht[i]=ht[i-1]*BASE+t[i];
for(int i=0;i<pos.size();i++){
if(s[pos[i]]=='*')
for(int j=1;j<t.size();j++)
if(dp[i][j-1]) dp[i][j]=1;
for(int j=0;j<t.size();j++){
if(!dp[i][j]) continue;
int st=pos[i]+1,ed=pos[i+1]-1,len=ed-st+1;
if(j+len<t.size()&&get_hs(st,ed)==get_ht(j+1,j+len)){
if(s[pos[i+1]]=='?') dp[i+1][j+len+1]=1;
else dp[i+1][j+len]=1;
}
}
}
if(dp[pos.size()-1][t.size()-1]) return "YES";
else return "NO";
}
int main(){
cin>>s>>n;
s='#'+s+'?',pos.push_back(0);
for(int i=1;i<s.size();i++)
if(s[i]=='*'||s[i]=='?') pos.push_back(i);
init_hash();
while(n--){
string t; cin>>t;
cout<<sol(t)<<'\n';
}
return 0;
}
T3 是双倍经验。
作业 T1
求方案数，考虑 dp。
我们钦定碱基串为 \(S\)，当前选的碱基序列为 \(T\)。
令 \(dp_{i,j}\) 表示前 \(i\) 个集合选出的字符串拼接起来后与 \(s_{1 \sim j}\) 的匹配方案数。
初始状态：\(dp_{0,i}=1\)，答案：\(\sum dp_{k,i}\)。
转移：
\[dp_{i,j}=(dp_{i,j}+dp_{i-1,j-len}) \bmod 10^9 +7 \]（\(len\) 为 \(T\) 的长度）
条件：
\[hs(j-len+1,j)+ht \]（\(hs(l,r)\) 表示 \(S_{l \sim r}\) 的 hash value，\(ht\) 表示 \(T\) 的 hash value）
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int K=1e2+5,A=11,S=1e4+5;
const int MOD=1e9+7,BASE=13331;
int n,k,ans;
int dp[K][S],a[K];
ull hs[S],ht[K][A],p[S];
string s,t[K][A];
void init_hash(){
p[0]=1;
for(int i=1;i<=n;i++) p[i]=p[i-1]*BASE;
for(int i=1;i<=n;i++) hs[i]=hs[i-1]*BASE+s[i];
for(int i=1;i<=k;i++)
for(int j=1;j<=a[i];j++)
for(int p=1;p<t[i][j].size();p++)
ht[i][j]=ht[i][j]*BASE+t[i][j][p];
}
ull get_hs(int l,int r){
return hs[r]-hs[l-1]*p[r-l+1];
}
signed main(){
cin>>k>>s,n=s.size(),s='#'+s;
for(int i=1;i<=k;i++){
cin>>a[i];
for(int j=1;j<=a[i];j++)
cin>>t[i][j],t[i][j]='#'+t[i][j];
}
init_hash();
for(int i=0;i<=n;i++) dp[0][i]=1;
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
for(int u=1;u<=a[i];u++){
int len=t[i][u].size()-1;
if(j>=len&&get_hs(j-len+1,j)==ht[i][u])
dp[i][j]=(dp[i][j]+dp[i-1][j-len])%MOD;
}
}
}
for(int i=1;i<=n;i++) ans=(ans+dp[k][i])%MOD;
cout<<ans;
return 0;
}