容易發(fā)現(xiàn)通配符中間的部分可以任意匹配，會造成的無法匹配的僅僅是前后綴，前綴和后綴可以分別獨立處理。如果字符串均有通配符，只需要按前/后綴長度排序然后暴力匹配就可以了。

　　問題在于存在無通配符的字符串。顯然首先這些字符串需要相同。剩下的字符串只要都能與該字符串匹配即可。然后就不會了。想了半天去看題解……暴力哈希。為啥跑2e8這么自信啊。

　　bzoj莫名T。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> using namespace std; int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } #define N 100010 #define L 10000010 #define ul unsigned long long int T,n,pre[N],suf[N],id[N]; ul hash[2][L],p[L]; vector<char> s[N]; bool isac(char c){return c>='a'&&c<='z'||c>='0'&&c<='9'||c=='*';} bool cmp(const int&a,const int&b) {return pre[a]<pre[b]; } bool check(int n) {for (int i=1;i<=n;i++) id[i]=i;sort(id+1,id+n+1,cmp);for (int i=2;i<=n;i++)for (int j=0;j<pre[id[i-1]];j++)if (s[id[i-1]][j]!=s[id[i]][j]) return 0;return 1; } ul gethash(int k,int l,int r) {if (l>r) return 0;return hash[k][r]-hash[k][l-1]*p[r-l+1]; } int main() { #ifndef ONLINE_JUDGEfreopen("bzoj3574.in","r",stdin);freopen("bzoj3574.out","w",stdout);const char LL[]="%I64d\n"; #elseconst char LL[]="%lld\n"; #endifT=read();p[0]=1;for (int i=1;i<=L-10;i++) p[i]=p[i-1]*509;while (T--){n=read();for (int i=1;i<=n;i++){s[i].clear();char c=getchar();while (!isac(c)) c=getchar();while (isac(c)) s[i].push_back(c),c=getchar();}hash[0][0]=0;int len=0;bool flag=1;for (int i=1;i<=n;i++){int l=s[i].size();pre[i]=l,suf[i]=-1;for (int j=0;j<l;j++)if (s[i][j]=='*') {pre[i]=j;break;}for (int j=l-1;~j;j--)if (s[i][j]=='*') {suf[i]=j;break;}if (pre[i]==l)if (!len){len=l;for (int j=0;j<l;j++) hash[0][j+1]=hash[0][j]*509+s[i][j];}else{ul tot=0;for (int j=0;j<l;j++) tot=tot*509+s[i][j];if (tot!=hash[0][len]) {flag=0;break;}}}if (!flag) {cout<<"N\n";continue;}if (!len){if (!check(n)) {cout<<"N\n";continue;}for (int i=1;i<=n;i++){reverse(s[i].begin(),s[i].end());pre[i]=(int)s[i].size()-suf[i]-1;}if (!check(n)) {cout<<"N\n";continue;}cout<<"Y\n";}else{bool flag=0;for (int i=1;i<=n;i++)if (pre[i]!=s[i].size()){hash[1][0]=0;int l=s[i].size();for (int j=0;j<l;j++) hash[1][j+1]=hash[1][j]*509+s[i][j];if (pre[i]+l-1-suf[i]>len||gethash(0,1,pre[i])!=gethash(1,1,pre[i])||gethash(0,len-l+suf[i]+2,len)!=gethash(1,suf[i]+2,l)) {flag=1;break;}int x=pre[i]+1;flag=1;for (int j=pre[i];j<=suf[i];j++){if (j==suf[i]) flag=0;if (s[i][j]=='*') continue;int t=j;while (s[i][t+1]!='*') t++;while (x+t-j<len-l+suf[i]+2&&gethash(0,x,x+t-j)!=gethash(1,j+1,t+1)) x++;if (x+t-j>=len-l+suf[i]+2) break;j=t;}if (flag) break; }if (flag) cout<<"N\n";else cout<<"Y\n";}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Gloid/p/9710851.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3574 HNOI2014抄卡组（哈希）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。