BZOJ2806: [Ctsc2012]Cheat

23333

調了好久發現是字尾邊搞錯了。。。

DP我是直接Copy别人的。。。

反正就是SAM+DP嘛。。。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
 
struct Node
{
    Node *last;
    Node *ch[3];
    int len;
    Node(){len=0;last=ch[0]=ch[1]=ch[2]=NULL;}
};
int n,m;
Node *last,*root;
inline void Begin()
{last=root=new Node;}
inline void add(int data)
{
    Node *tp,*ne=new Node;
    ne->len=last->len+1;
    for(tp=last;tp&&!tp->ch[data];tp=tp->last)
       tp->ch[data]=ne;
    last=ne;
    if(!tp)
       ne->last=root;
    else if(tp->len==tp->ch[data]->len-1)
       ne->last=tp->ch[data];
    else
         {
            Node *a=tp->ch[data],*b=new Node;
            *b=*a;b->len=tp->len+1;
            ne->last=a->last=b;
            for(;tp&&tp->ch[data]==a;tp=tp->last)tp->ch[data]=b;
         }
     
}
inline void insert(int *S,int n)
{
    int i=1;
    //Node *tp=root;
//  for(i=1;i<=n&&tp->ch[S[i-1]];i++)
     // tp=tp->ch[S[i-1]];
    //last=tp;
    add(2);
    for(;i<=n;i++)add(S[i-1]);
}
char c;
inline void read(int &a){a=0;do c=getchar();while(c<'0'||c>'9');while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();}
int Cache[2000010];
inline void in()
{   
    int len=0;
    do
    Cache[0]=getchar()-'0';
    while(Cache[0]!=0&&Cache[0]!=1);
    do
    Cache[++len]=getchar()-'0'; 
    while(Cache[len]==0||Cache[len]==1);
    insert(Cache,len);
}
int Val[10000001];
int dp[10000001];
struct L
{
    int l,r;
    int Line[100001];
    L(){l=r=0;}
    inline bool empty(){return r<=l;}
    inline void push(int a){Line[r++]=a;}
    inline void pop(){++l;}
    inline int front() {return Line[l];}
    inline void clear(){l=r=0;}
}q;
 
 
inline bool Check(int L,int len)
{   
    dp[0] = 0;
    q.clear();
    for(int i = 1; i <= len; i++) {
        dp[i] = dp[i-1];
        int p = i-L;
        if(p >= 0) {
            while(!q.empty() && dp[p]-p >= dp[q.front()] - q.front())
                q.pop();
            q.push(p);
        }
        while(!q.empty() && i-Val[i] > q.front()) q.pop();
        if(!q.empty()) dp[i] = max(dp[i], dp[q.front()]+i-q.front());
    }
    return 10*dp[len] >= 9*len;
}
 
 
int main()
{
    Begin();
    read(n),read(m);
    while(m--)in();
    int *base=Cache;
    while(n--)
    {
    int len=0;
    do base[0]=getchar()-'0';while(Cache[0]!=0&&Cache[0]!=1);
    do base[++len]=getchar()-'0';   while(Cache[len]==0||Cache[len]==1);
    int i;
    Node *tp=root;
    int cur=0;
    for(i=0;i<len;i++)
       {
          if(tp->ch[base[i]])
              tp=tp->ch[base[i]],cur++;
          else
              {
              while(tp&&!tp->ch[base[i]])
                      tp=tp->last;
                if(tp==NULL)tp=root,cur=0;
                 else
                  cur=tp->len+1,tp=tp->ch[base[i]];  
              }
          Val[i+1]=cur;
       }
    int mid,l=0,r=len;
    while(l<r-1)
    {
      mid=(l+r)>>1;
      if(Check(mid,len))
         l=mid;
        else r=mid-1;
    }
    if(Check(r,len))
       printf("%d\n",r);
    else printf("%d\n",l);
    }
    return 0;
}