偷懒直接把bzoj的网页内容ctrlcv过来了

2806: [Ctsc2012]Cheat

Time Limit: 20 Sec  Memory Limit: 256 MB

Submit: 1943  Solved: 1004

[][][]

Description

Input

第一行两个整数N，M表示待检查的作文数量，和小强的标准作文库

的行数

接下来M行的01串，表示标准作文库

接下来N行的01串，表示N篇作文

Output

N行，每行一个整数，表示这篇作文的Lo 值。

Sample Input

1 2

10110

000001110

1011001100

Sample Output

4

HINT

输入文件不超过1100000字节

注意：题目有改动,可识别的长度不小于90%即可，而不是大于90%

---

 

 

所谓少于$1.1*10^6$就是总输入字符数少于这个数...

果然CTSC出的题水平够高

专门爆踩SAM只学了板子不懂各个元素含义和应用的菜鸡(像我这样的就是了)

随便把模式串扔进广义SAM里

答案L0具有单调性

所以二分答案

接下来考虑$O(n)$求出最长匹配长度

$O(n)$的话...只能dp了啊

在SAM上跑字符串匹配求出每一位的最长向前匹配长度$f[i]$

用$dp[i]$表示到i位置匹配了多少字符

之后有dp方程

$dp[i]=max(dp[i-1],max(dp[j=(i-f[i]) to (i-L0)]+i-j))$

对于$dp[j]-j$,$O(n^2)$单调队列优化变成$O(n)$

本题完结

1 #include
       
          2 #include
        
           3 #include
         
            4 using std::queue;  5 const int N=1100011;  6 char sin[N];  7 int nn,nm,n;  8 template
          
           tp max(tp a,tp b){
     return a>b?a:b;}  9  10 struct sam 11 { 12     int tranc[2],len,pre; 13 }s[N<<1]; 14  15 struct Sakuya_Brando 16 { 17     int size,fin; 18     Sakuya_Brando(){size=1;} 19     void insert(int ch) 20     { 21         int npx,npy,lpx,lpy; 22         if(s[fin].tranc[ch]) 23         { 24             lpx=fin,lpy=s[fin].tranc[ch]; 25             if(s[lpy].len==s[lpx].len+1) fin=lpy; 26             else 27             { 28                 npy=++size; 29                 s[npy]=s[lpy]; 30                 s[npy].len=s[lpx].len+1; 31                 s[lpy].pre=npy; 32                 while(s[lpx].tranc[ch]==lpy) 33                 { 34                     s[lpx].tranc[ch]=npy; 35                     lpx=s[lpx].pre; 36                 } 37                 fin=npy; 38             } 39             return; 40         } 41         npx=++size; 42         s[npx].len=s[fin].len+1; 43         for(lpx=fin;lpx&&!s[lpx].tranc[ch];lpx=s[lpx].pre) s[lpx].tranc[ch]=npx; 44         if(!lpx) s[npx].pre=1; 45         else 46         { 47             lpy=s[lpx].tranc[ch]; 48             if(s[lpy].len==s[lpx].len+1) s[npx].pre=lpy; 49             else 50             { 51                 npy=++size; 52                 s[npy]=s[lpy]; 53                 s[npy].len=s[lpx].len+1; 54                 s[lpy].pre=s[npx].pre=npy; 55                 while(s[lpx].tranc[ch]==lpy) 56                 { 57                     s[lpx].tranc[ch]=npy; 58                     lpx=s[lpx].pre; 59                 } 60             } 61         } 62         fin=npx; 63     } 64     void ins(char *str,int len) 65     { 66         fin=1; 67         len=strlen(str); 68         for(int i=0;i
           
            =len*9) return 1;118     else return 0;119 }120 121 int main()122 {123     scanf("%d%d",&nn,&nm);124     for(int i=1;i<=nm;i++)125     {126         scanf("%s",sin);127         n=strlen(sin);128         sakuya.ins(sin,n);129     }130     for(int i=1;i<=nn;i++)131     {132         scanf("%s",sin);133         n=strlen(sin);134         bao0(sin,n);135         int l0=0,r0=n;136         while(l0
            
             >1;139 if(check(sin,mid,n)) l0=mid;140 else r0=mid-1;141 }142 noi(sin,n);143 printf("%d\n",l0);144 }145 return 0;146 }