bzoj 2119 股市的预测 —— 枚举关键点+后缀数组

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2119

思路就是对于这个形如 ABA 的串，枚举 A 的长度，并按照长度分出几块，找到一些关键点就是块的开头；

那么每一种 ABA 的串，A 的部分一定覆盖了一个关键点；

所以找关键点周围的匹配长度算答案，具体就是找和对应位置的 lcp + lcs，那么 ABA 可以在对应匹配的地方滑动，就能找到所有 ABA 了；

因为是差分数组所以 n-1，而且注意连接正反串的字符要比串内字符小，不是 '0'-1 而是 0 ...

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

int Min(int x,int y){return x<y?x:y;}

int const xn=1e5+;

int n,mx,d,m,s[xn],t[xn],tt[xn],tax[xn],sa[xn],rk[xn],tp[xn];

int op[xn],ht[xn][],bin[],bit[xn];

void rsort()

{

  for(int i=;i<=m;i++)tax[i]=;

  for(int i=;i<=mx;i++)tax[rk[tp[i]]]++;

  for(int i=;i<=m;i++)tax[i]+=tax[i-];

  for(int i=mx;i;i--)sa[tax[rk[tp[i]]]--]=tp[i];

}

void work()

{

  for(int i=;i<=mx;i++)rk[i]=s[i],tp[i]=i;

  m=n; rsort();

  for(int k=;k<=mx;k<<=)

    {

      int num=;

      for(int i=mx-k+;i<=mx;i++)tp[++num]=i;

      for(int i=;i<=mx;i++)

    if(sa[i]>k)tp[++num]=sa[i]-k;

      rsort(); swap(rk,tp);

      rk[sa[]]=; num=;

      for(int i=;i<=mx;i++)

    rk[sa[i]]=(tp[sa[i]]==tp[sa[i-]]&&tp[sa[i]+k]==tp[sa[i-]+k])?num:++num;

      if(num==mx)break;

      m=num;

    }

}

void geth()

{

  int k=;

  for(int i=;i<=mx;i++)

    {

      if(rk[i]==)continue;

      if(k)k--; int j=sa[rk[i]-];

      while(s[i+k]==s[j+k]&&i+k<=mx&&j+k<=mx)k++;

      ht[rk[i]][]=k;

    }

  bin[]=; for(int i=;i<;i++)bin[i]=(bin[i-]<<);

  bit[]=; for(int i=;i<=mx;i++)bit[i]=bit[i>>]+;

  for(int i=;i<;i++)

    for(int j=;j+bin[i]-<=mx;j++)

      ht[j][i]=Min(ht[j][i-],ht[j+bin[i-]][i-]);

}

int getlcp(int x,int y)

{

  if(x==y)return mx-x+;

  x=rk[x]; y=rk[y];

  if(x>y)swap(x,y); x++;

  int r=bit[y-x+];

  return Min(ht[x][r],ht[y-bin[r]+][r]);

}

int main()

{

  n=rd(); d=rd();

  for(int i=;i<=n;i++)t[i]=rd();

  for(int i=n;i>;i--)t[i]=t[i]-t[i-],tt[i]=t[i];

  sort(t+,t+n+); int tot=unique(t+,t+n+)-t-;

  for(int i=;i<=n;i++)tt[i]=lower_bound(t+,t+tot+,tt[i])-t;

  n--; mx=*n+;

  for(int i=;i<=n;i++)s[i]=tt[i+];

  s[n+]=;//

  for(int i=n+,k=n;k;i++,k--)s[i]=s[k],op[k]=i;

  work(); geth(); int ans=;

  for(int k=;k<=n;k++)

    for(int i=;i+k+d<=n;i+=k)

      {

    int j=i+k+d;

    int l1=getlcp(i,j),l2=getlcp(op[i],op[j]);

    l1=Min(l1,k); l2=Min(l2,k);

    if(l1&&l2&&l1+l2->=k)ans+=l1+l2--k+;

    else if(l1&&l1>=k)ans+=l1-k+;

    else if(l2&&l2>=k)ans+=l2-k+;

      }

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

  return ;

}