洛谷P3234 抄卡组 [HNOI2014] 字符串hash

正解:字符串hash

解题报告:

传送门!

字符串hash是字符串匹配中很常见的一个方法,原理也很好懂,这里就不做太多阐述辣有时间放到hash笔记里面去QAQ

题意不说了挺好理解的,自带一句话概括好评

然后直接说正解QAQ

首先要想到对于读入,有三种情况

第一种,麻油有通配符的,这种最简单,直接读的时候判断一下就好

第二种,全都有通配符,显然这样的情况下,只要前后缀都是一样的,中间一定能用通配符操作一番之后变成一样的,只要判断前缀后缀就好

第三种,有的有通配符有的麻油,这种情况相对来说复杂一些,首先可以把麻油的按照第一种的判断了,然后把有的和麻油的匹配一下,匹配的话只要看通配符之间的484都相等就好

然后想到之后实现一下就好了,,,没了,,,

#include
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
{vectorhsh,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+1if(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 >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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！