KMP刷题记录

【BZOJ4698】[SDOI2008]Sandy的卡片

• 差分一下然后选一个串，用这个串的所有前缀和其他串kmp，求出最长的公共部分即可
• 代码：
  

   1 #include <bits/stdc++.h>
   2 #define f(c,a,b) for (int c=a; c<=b; c++)
   3 #define nmax 1010
   4  
   5 using namespace std;
   6 int n;
   7 int a[nmax][nmax];
   8 int b[nmax], nex[nmax], l[nmax];
   9  
  10 void buildnext(int lb){
  11     nex[0] = -1;
  12     nex[1] = 0;
  13     f(i,2,lb){
  14         int j = nex[i-1];
  15         for(;b[j+1]!=b[i]&&j>=0; j=nex[j]);
  16         nex[i] = j+1;
  17     }
  18 }
  19  
  20 int kmp(int lb, int id){
  21     int ans=0;
  22     int j=0;
  23     f(i,1,l[id]){
  24         for(;b[j+1]!=a[id][i]&&j>=0; j=nex[j]);
  25         j++;
  26         ans = max(j,ans);
  27     }
  28     return ans;
  29 }
  30  
  31 int main(){
  32     int ans=0;
  33     cin >> n;
  34     f(i,1,n){
  35         scanf("%d", &l[i]);
  36         f(j,1,l[i]) scanf("%d", &a[i][j]);
  37         f(j,2,l[i]) a[i][j-1]=a[i][j]-a[i][j-1];
  38         l[i]--;
  39     }
  40     f(i,1,l[1]){
  41         int c=0;
  42         f(j,i,l[1]) b[++c]=a[1][j];
  43         buildnext(c);
  44         int ta=nmax;
  45         f(j,2,n) ta = min( kmp(c,j), ta );
  46         ans = max(ans, ta);
  47     }
  48     printf("%d\n",ans+1);
  49     return 0;
  50 }

  ??

   

KMP刷题记录

原文：https://www.cnblogs.com/jiecaoer/p/12245098.html