一本通 1469：似乎在梦中见过的样子

对于字符串S, 求有多少合法子串（ 该子串形式为 ABA， len(B)>=1, len(A) >=K) 

lenS =15e3

谁能想到这题是暴力n^2

直接n^2枚举 l,r ,预处理出kmp的next[ ] ,逐个判断

#include <bits/stdc++.h>
using namespace std ; 
const int N=15e3+5;
 char s[N];
 int n,p[N],L;
 int f[N];
 
 void solve(){
     int i,j,k;
     int ans=0;
     
     for(i=1;i<n;i++){
         memset(p,0,sizeof p);
         p[i]=i-1;
         k=i-1;
         for(j=i+1;j<=n;j++){
             while(k>=i&&s[j]!=s[k+1]) k=p[k];
             if(s[j]==s[k+1]) k++;
             p[j]=k;
         }
         for(j=i;j<=n;j++){
             k=p[j];
             while(k-i+1>=L){
                 if((k-i+1)*2+1<=(j-i+1)){ ans++;break;}
                k=p[k];
             }
         }
     }
     cout<<ans;
 }
 int main(){
     cin>>s+1>>L; n=strlen(s+1);
     solve();
 }