[BZOJ4698] [SDOI2008]Sandy 的卡片
差分一下然后选一个串, 用这个串的所有前缀和其他串 kmp, 求出最长的公共部分即可
代码:
- #include <bits/stdc++.h>
- #define f(c,a,b) for (int c=a; c<=b; c++)
- #define nmax 1010
- using namespace std;
- int n;
- int a[nmax][nmax];
- int b[nmax], nex[nmax], l[nmax];
- void buildnext(int lb){
- nex[0] = -1;
- nex[1] = 0;
- f(i,2,lb){
- int j = nex[i-1];
- for(;b[j+1]!=b[i]&&j>=0; j=nex[j]);
- nex[i] = j+1;
- }
- }
- int kmp(int lb, int id){
- int ans=0;
- int j=0;
- f(i,1,l[id]){
- for(;b[j+1]!=a[id][i]&&j>=0; j=nex[j]);
- j++;
- ans = max(j,ans);
- }
- return ans;
- }
- int main(){
- int ans=0;
- cin>> n;
- f(i,1,n){
- scanf("%d", &l[i]);
- f(j,1,l[i]) scanf("%d", &a[i][j]);
- f(j,2,l[i]) a[i][j-1]=a[i][j]-a[i][j-1];
- l[i]--;
- }
- f(i,1,l[1]){
- int c=0;
- f(j,i,l[1]) b[++c]=a[1][j];
- buildnext(c);
- int ta=nmax;
- f(j,2,n) ta = min( kmp(c,j), ta );
- ans = max(ans, ta);
- }
- printf("%d\n",ans+1);
- return 0;
- }
- ??
来源: http://www.bubuko.com/infodetail-3400731.html