[CTSC2012] 익숙한 글

제목의 뜻


여러 개의 주열이 있고, 매번 문의할 때마다 질문열을 여러 개의 연속 서브열로 나누며, 만약 한 서브열의 길이가 ≥L≥L이고 주열에 나타난 적이 있다면 합법적이다
만약 합법적인 하위 문자열의 총 길이가 ≥≥ 질문 문자열의 90% 90%라면 이 문자열은 합법적인 문자열입니다. 질문 문자열이 합법적인 문자열의 최대 L L이 되도록 하십시오.

문제풀이


먼저 넓은 의미의 SAM, S A M을 세우고 L L이 단조성을 만족시키는 것을 발견하면 2점 답안을 얻을 수 있다.
어떻게 check c h e c k 용 dp
폭력을 고려한 DP, f[i] D P, f[i]는 앞의 i 문자가 가장 길고 합법적인 길이를, maci m a c i는 i와 일치하는 가장 긴 공통 문자열의 길이를 나타낸다(넓은 의미의 SAM S A M에서 [spoj1812] LCS2 [S p o j1812] L C S 2)
⇒f[i]=max{f[i−1],f[j]+j−i,j∈[i−maci,i−L]} ⇒ f [ i ] = m a x { f [ i − 1 ] , f [ j ] + j − i , j ∈ [ i − m a c i , i − L ] }
i -3 L i -3 L은 단조롭게 증가하는 것을 발견할 수 있고, i -3 maci i -3 m a c i는 단조롭게 증가하지 않기 때문에 단조로운 대기열을 사용하여 O (n) O (n)로 최적화할 수 있다.
#include
#define fp(i,a,b) for(register int i=a,I=b+1;i
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
templateinline bool cmax(T&a,const T&b){return a1:0;}
templateinline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
templateinline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='
'
; } const int N=1e6+5,M=2*N; typedef long long ll; typedef int arr[M]; struct SAM{ int las,T,ch[M][2];arr fa,len; SAM(){las=T=1;} inline void ins(int c){ int p=las,np;fa[las=np=++T]=1,len[np]=len[p]+1; for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np; if(p){ int q=ch[p][c],nq; if(len[p]+1==len[q])fa[np]=q; else{ fa[nq=++T]=fa[q],len[nq]=len[p]+1,memcpy(ch[nq],ch[q],4*2); for(fa[q]=fa[np]=nq;ch[p][c]==q;p=fa[p])ch[p][c]=nq; } } } int n,mac[N],f[N],q[N];char s[N]; inline void Match(){ int x=1,l=0,c; fp(i,1,n){ c=s[i]-'0';while(x&&!ch[x][c])x=fa[x],l=len[x]; if(x)x=ch[x][c],++l;else x=1,l=0;mac[i]=l; } } inline bool chk(int L){ int h=1,t=0; fp(i,1,L-1)f[i]=0; fp(i,L,n){f[i]=f[i-1]; while(h<=t&&f[q[t]]-q[t]q[++t]=i-L;while(h<=t&&q[h]if(h<=t)cmax(f[i],f[q[h]]+i-q[h]); } return f[n]*10>=n*9; } inline void sol(){ scanf("%s",s+1);n=strlen(s+1);Match(); int L=0,R=n,ans=0,mid; while(L<=R){ mid=(L+R)>>1; if(chk(mid))ans=mid,L=mid+1; else R=mid-1; } printf("%d
"
,ans); } }p; int n,m;char s[N]; int main(){ #ifndef ONLINE_JUDGE file("s"); #endif scanf("%d%d",&n,&m); fp(i,1,m){ scanf("%s",s),p.las=1; fp(j,0,strlen(s)-1)p.ins(s[j]-'0'); } while(n--)p.sol(); return Ot(),0; }

좋은 웹페이지 즐겨찾기