正解:字符串hash
解题报告:
传送门!
字符串hash是字符串匹配中很常见的一个方法,原理也很好懂,这里就不做太多阐述辣有时间放到hash笔记里面去QAQ
题意不说了挺好理解的,自带一句话概括好评
然后直接说正解QAQ
首先要想到对于读入,有三种情况
第一种,麻油有通配符的,这种最简单,直接读的时候判断一下就好
第二种,全都有通配符,显然这样的情况下,只要前后缀都是一样的,中间一定能用通配符操作一番之后变成一样的,只要判断前缀后缀就好
第三种,有的有通配符有的麻油,这种情况相对来说复杂一些,首先可以把麻油的按照第一种的判断了,然后把有的和麻油的匹配一下,匹配的话只要看通配符之间的484都相等就好
然后想到之后实现一下就好了,,,没了,,,
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define fr first
#define sc second
#define rg register
#define gc getchar()
#define mp make_pair
#define ll unsigned long long
#define rp(i,x,y) for(rg int i=x;i<=y;++i)
#define my(i,x,y) for(rg int i=x;i>=y;--i)
const ll bas=10162003,N=100000+10,L=1e7+10;const bool gdgs=1;
ll powbs[L]={1};
struct node
{
vector<ll>hsh,hv;bool ishv;int lth;
il void rd()
{
char ch=gc;hsh.clear();hv.clear();ishv=0;lth=0;hsh.push_back(0);while(ch=='\n' || ch=='\r')ch=gc;
while(ch!='\n' && ch!='\r'){++lth;hsh.push_back(hsh[lth-1]*bas+ch);if(ch=='*')hv.push_back(lth);ch=gc;}
ishv=hv.size();
}
il ll gths(){return hsh[lth];}
il int gtfr(){return ishv?hv[0]:-1;}
il int gtlst(){return ishv?lth-(*--hv.end()):-1;}
il ll cal(int l,int r){return (l<=0 || r>lth)?-1:hsh[r]-hsh[l-1]*powbs[r-l+1];}
}cd[N];
il int read()
{
rg char ch=gc;rg int x=0;rg bool y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il void pre(){rp(i,1,1e7+3)powbs[i]=powbs[i-1]*bas;}
il bool mch(int x,int y)
{
int l=cd[x].gtfr();if(cd[x].cal(1,l-1)!=cd[y].cal(1,l-1))return 0;
int r=cd[x].gtlst()-1;if(cd[x].cal(cd[x].lth-r,cd[x].lth)!=cd[y].cal(cd[y].lth-r,cd[y].lth))return 0;
int p1=0,p2=l;
while(p1+1<cd[x].hv.size() && p2+r<cd[y].lth)
{
int lth=cd[x].hv[p1+1]-cd[x].hv[p1]-1;ll num=cd[x].cal(cd[x].hv[p1]+1,cd[x].hv[p1+1]-1);
while(gdgs){if(p2+lth-1+r>=cd[y].lth)return 0;if(cd[y].cal(p2,p2+lth-1)==num){++p1,p2+=lth;break;}++p2;}
}
return (p1+1==cd[x].hv.size());
}
il void wk()
{
int n=read(),lst=0;bool as=1;rp(i,1,n){cd[i].rd();if(!cd[i].ishv){if(lst && cd[lst].gths()!=cd[i].gths())as=0;lst=i;}}
if(!as)return void(printf("N\n"));
if(!lst)
{
vector< pair<int,int> >cal;
cal.clear();rp(i,1,n)cal.push_back(mp(cd[i].gtfr()-1,i));sort(cal.begin(),cal.end());
rp(i,1,n-1)if(cd[cal[i].sc].cal(1,cal[i-1].fr)!=cd[cal[i-1].sc].cal(1,cal[i-1].fr))return void(printf("N\n"));
cal.clear();rp(i,1,n)cal.push_back(mp(cd[i].gtlst(),i));sort(cal.begin(),cal.end());
rp(i,1,n-1)if(cd[cal[i].sc].cal(cd[cal[i].sc].lth-cal[i-1].fr+1,cd[cal[i].sc].lth)!=cd[cal[i-1].sc].cal(cd[cal[i-1].sc].lth-cal[i-1].fr+1,cd[cal[i-1].sc].lth))return void(printf("N\n",i));
return void(printf("Y\n"));
}
rp(i,1,n)if(cd[i].ishv)if(!mch(i,lst))return void(printf("N\n"));return void(printf("Y\n"));
}
int main()
{
// freopen("ckz.in","r",stdin);freopen("ckz.out","w",stdout);
pre();int T=read();while(T--)wk();
return 0;
} 
