题解 P3234 【[HNOI2014]抄卡组】
斯德哥尔摩
2018-09-23 20:51:07
[P3234 [HNOI2014]抄卡组](https://www.luogu.org/problemnew/show/P3234)
趁没有题解赶紧抢一血。。。
题目已经解释得很清楚了，一个带通用字符的字符转匹配。
一开始看到多模式串，不由自主地想起了$AC$自动机/$SAM$。
然而看了下数据范围：$N\times \max_{i=1}^n\{ Length(str_i) \}<=10^8$
这还怎么$AC$自动机啊。。。
不知道怎么做，开始$YY$~~（其实就是翻题解。。。）~~
我是啃这位巨佬的题解看懂的：[链接](https://blog.csdn.net/jiangyuze831/article/details/42294833)
好神啊，$KMP$都不用，直接$hash$。。。
首先，对于那个坑爹的数据范围，我们使用$vector$来~~搞事~~解决。
然后我们计算出每个字符串的$hash$值。
（据说单$hash$会被卡，这里由于数据不卡，我们自行忽略。。。如果实在想写也可以。）
然后分类讨论：
1. 所有的字符串中都不含通配符。
这种情况好办，直接比较我们算出来的$hash$值即可。
怎么比？当然排个序然后相邻两位比较啊。。。
2. 所有字符串都含有通配符。
注意到通配符可以代替任意字符串。
那么我们就可以不管中间的通配符了，只需要看前缀和后缀。
前缀是从开头到第一个通配符，后缀同理。
按照前缀从短到长排序，然后逐个判断前缀是否相等，后缀同理。
中间的通配符肯定有一种方案搞成匹配的。
3. 部分字符串都含有通配符。
首先，把不含有通配符的字符串比较一下。
然后让所有含有通配符的字符串变成不含有通配符的字符串。
怎么变呢？
我们按照上一种情况的想法，先把前缀和后缀去掉。
然后让含有通配符的那个的中间部分匹配上不含有通配符的中间部分的字符串即可。
上面已经说了，中间的通配符肯定有一种方案搞成匹配的。
所以是可行的。
怎么搞呢？
直接暴力就行辣！反正怎么弄都是$O(n)$。。。
利用通配符分割含有通配符的中间部分，然后用一个指针去扫不含有通配符的字符串。
于是这个问题也被愉快地解决了！
到此，我们对这个问题的分析结束。
但是$STL$常数较大怎么办？我们的$vector,string$是肯定不能动的。。。
只剩下常数巨大的$O(n)$的暴力与读入，并且常数巨大的暴力好像也没有什么优化的余地。。。
那就只剩读入了。。。
读入优化？可以。
但是我们同样可以关闭流的同步。
也就是在$main$函数开头添加一句：
```cpp
ios::sync_with_stdio(false);
```
然后就可以了！
附上代码（缩进好丑。。。）：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#define MAXN 100010
#define MAXM 10000010
#define base 2333//hash
using namespace std;
int n;
unsigned long long val[MAXM];//使用unsigned long long的自动溢出
bool flag;
string ch;
struct String{//自定义字符串
int len,num;
vector<unsigned long long> hash;//记录hash值
vector<int> word;//记录每个通配符的出现位置
friend bool operator <(const String p,const String q){
return (flag?(p.word[1]<q.word[1]):(p.len-p.word[p.num]<q.len-q.word[q.num]));
}
inline void init(){//清空
len=num=0;
hash.clear();hash.push_back(0);
word.clear();word.push_back(0);
}
void build(string s){//计算hash值
for(string::iterator it=s.begin();it!=s.end();it++){
hash.push_back(hash.back()*base+*it);
len++;
if(*it=='*'){
num++;
word.push_back(len);
}
}
}
unsigned long long get_hash(int l,int r)const{return hash[r]-hash[l-1]*val[r-l+1];}
int get_suffix()const{return len-word[num];}
bool match(const String &s){//暴力匹配
int suffix=get_suffix();
if(s.len<suffix+word[1]-1)return false;
if(get_hash(1,word[1]-1)!=s.get_hash(1,word[1]-1))return false;
if(get_hash(word[num]+1,len)!=s.get_hash(s.len-suffix+1,s.len))return false;
int l=word[1],r=s.len-suffix;//两个指针扫
for(int i=1;i<num;i++){
int length=word[i+1]-word[i]-1;
unsigned long long t=get_hash(word[i]+1,word[i+1]-1);
while(1){//变成一样的字符串
if(l+length-1>r)return false;
if(s.get_hash(l,l+length-1)==t){l+=length;break;}
l++;
}
}
return true;
}
}str[MAXN];
inline void make(){//预处理hash
val[0]=1;
for(int i=1;i<=MAXM-10;i++)val[i]=val[i-1]*base;//当初把MAXM打成了MAXN，然后WA了无数次。。。吃枣药丸。。。
}
bool check(){//分类讨论
int pos=0;
unsigned long long hash_val=0;
for(int i=1;i<=n;i++){
if(str[i].num)continue;
if(!pos){
hash_val=str[i].hash[str[i].len];
pos=i;
}
else if(hash_val!=str[i].hash[str[i].len])return false;
}
if(pos){
for(int i=1;i<=n;i++)if(str[i].num&&(!str[i].match(str[pos])))return false;
}
else{
flag=true;
sort(str+1,str+n+1);
for(int i=1;i<n;i++)
if(str[i].get_hash(1,str[i].word[1]-1)!=str[i+1].get_hash(1,str[i].word[1]-1))
return false;
flag=false;
sort(str+1,str+n+1);
for(int i=1;i<n;i++)
if(str[i].get_hash(str[i].word[str[i].num]+1,str[i].len)!=str[i+1].get_hash(str[i+1].len-str[i].get_suffix()+1,str[i+1].len))
return false;
}
return true;
}
void work(){
if(check())putchar('Y');
else putchar('N');
putchar('\n');
}
void init(){//读入
cin>>n;
for(int i=1;i<=n;i++){
cin>>ch;
str[i].init();
str[i].build(ch);
}
}
int main(){//主函数So easy!
ios::sync_with_stdio(false);
int t;
cin>>t;
make();
while(t--){
init();
work();
}
return 0;
}
```