KMP刷题记录

2024-09-06 13:24:30

【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[] = -;

     nex[] = ;

     f(i,,lb){

         int j = nex[i-];

         for(;b[j+]!=b[i]&&j>=; j=nex[j]);

         nex[i] = j+;

     }

 }

 int kmp(int lb, int id){

     int ans=;

     int j=;

     f(i,,l[id]){

         for(;b[j+]!=a[id][i]&&j>=; j=nex[j]);

         j++;

         ans = max(j,ans);

     }

     return ans;

 }

 int main(){

     int ans=;

     cin >> n;

     f(i,,n){

         scanf("%d", &l[i]);

         f(j,,l[i]) scanf("%d", &a[i][j]);

         f(j,,l[i]) a[i][j-]=a[i][j]-a[i][j-];

         l[i]--;

     }

     f(i,,l[]){

         int c=;

         f(j,i,l[]) b[++c]=a[][j];

         buildnext(c);

         int ta=nmax;

         f(j,,n) ta = min( kmp(c,j), ta );

         ans = max(ans, ta);

     }

     printf("%d\n",ans+);

     return ;

 }
```
最新文章
热门文章