We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;#define MM 9000000charmark[20][100005];intL;constintinf=0x3F3F3F3F;typedeflonglonglint;chartext[11][100005];intx[11],best[1<<20],covered[1<<20];intCC;typedefstructN{intllen;structN*next[160];structN*fail;N(){llen=-1;for(inti=0;i<160;i++)next[i]=NULL;fail=NULL;}}Node;Node*root;Node*queue[MM+10];intfront,rear;charcommand[MM+10];inlineintidd(charch){return(int)ch;}voidInsert(char*s){intL=strlen(s);Node*cur=root;for(inti=0;i<L;i++){intt=idd(s[i]);if(cur->next[t]==NULL)cur=cur->next[t]=newNode();elsecur=cur->next[t];}cur->llen=max(cur->llen,(int)strlen(s));}voidAC_Make(){front=rear=0;queue[rear++]=root;while(rear>front){Node*cur=queue[front++];if(cur->fail!=NULL){cur->llen=max(cur->llen,cur->fail->llen);}for(inti=0;i<160;i++){if(cur->next[i]==NULL){cur->next[i]=(cur==root)?root:cur->fail->next[i];}else{cur->next[i]->fail=(cur==root)?root:cur->fail->next[i];queue[rear++]=cur->next[i];}}}}// make st to en as 0 inclusive!voidmz(intst,inten,intlev=0,intls=0,intle=L-1){if(en<ls||st>le)return;if(ls>=st&&le<=en||ls==le){//mark this range as 0mark[lev][ls]=0;return;}intmid=(ls+le)>>1;if(mid>=ls)mz(st,en,lev+1,ls,mid);if(mid+1<=le)mz(st,en,lev+1,mid+1,le);}boolisz(intid,intlev=0,intls=0,intle=L-1){if(id<ls||id>le||le<ls)returntrue;if(ls==le)returnmark[lev][ls];boolans=mark[lev][ls];if(!ans)returnans;intmid=(ls+le)>>1;if(mid>=ls&&id<=mid)ans&=isz(id,lev+1,ls,mid);elseif(mid+1<=le)ans&=isz(id,lev+1,mid+1,le);returnans;}// this will return the power of the current string!intquery(chars[]){memset(mark,-1,sizeofmark);L=strlen(s);Node*cur=root;for(inti=0;i<L;i++){cur=cur->next[idd(s[i])];if(cur->llen>0){mz(i-cur->llen+1,i);}}intans=0;for(inti=0;i<L;i++){if(isz(i)){ans++;}}returnans;}lintgetHighestUngettable(intM){lintret=-1;for(inti=1;i<M;++i)if(best[i]>=inf)return-1;elseret=max(ret,(best[i]-1)*(lint)M+i);returnret;}voidcomputeDistances2(intM,intn){for(inti=0;i<M;++i)best[i]=inf;best[0]=0;for(intj=0;j<n;++j){intc=x[j]/M,d=x[j]%M;if(d==0)continue;++CC;for(intstart=0;start<M;++start)if(covered[start]!=CC){intrep=1+(start>0);while(rep--){for(intl=(d+start)%M,prev=start;;prev=l,l=(l+d)){if(l>=M)l-=M;best[l]=min(best[l],c+best[prev]+(prev>l));covered[l]=CC;if(l==start)break;}}}}}intmain(){intm,n;scanf("%d\n",&n);for(inti=0;i<n;i++){gets(text[i]);intl=strlen(text[i]);if(text[i][l-1]=='\n')text[i][l-1]='\0';}root=newNode();scanf("%d\n",&m);for(inti=0;i<m;i++){gets(command);intl=strlen(command);if(command[l-1]=='\n')command[l-1]='\0';Insert(command);}AC_Make();for(inti=0;i<n;i++)x[i]=query(text[i]);sort(x,x+n);n=unique(x,x+n)-x;swap(x[0],x[n-1]);intM=x[n-1];computeDistances2(M,n-1);linth=getHighestUngettable(M);printf("%lld\n",h);return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Powercode
You are viewing a single comment's thread. Return to all comments →
C++ solution