【HDU4622】Reincarnation

题面

https://vjudge.net/problem/HDU-4622

题解

#include<cstdio>
#include<cstring>
#include<iostream>
#define ri register int
#define N 2050
using namespace std;

int T;
char s[N];
int ans[N][N],q;

struct SAM{
  int ff[N<<1],len[N<<1];
  int ch[N<<1][26];
  int tot,last,ans;
  inline void init() {
    memset(ch,0,sizeof(ch));
    last=tot=1;
    ans=0;
  }
  inline void extend(int c) {
    int p=last,np=++tot; last=np; len[np]=len[p]+1;
    while (p && !ch[p][c]) ch[p][c]=np,p=ff[p];
    if (!p) ff[np]=1;
    else {
      int q=ch[p][c];
      if (len[q]==len[p]+1) ff[np]=q;
      else {
        int nq=++tot;
        for (ri i=0;i<26;i++) ch[nq][i]=ch[q][i];
        ff[nq]=ff[q]; len[nq]=len[p]+1; ans+=len[nq]-len[ff[nq]];
        ans-=(len[q]-len[ff[q]]);
        ff[np]=ff[q]=nq;
        ans+=(len[q]-len[ff[q]]);
        while (p && ch[p][c]==q) ch[p][c]=nq,p=ff[p];
      }
    }
    ans+=len[np]-len[ff[np]];
  }
} sam;

int main() {
  scanf("%d",&T);
  while (T--) {
    scanf("%s",s+1);
    for (ri i=1,l=strlen(s+1);i<=l;i++) {
      sam.init();
      for (ri j=i;j<=l;j++) {
        sam.extend(s[j]-'a');
        ans[i][j]=sam.ans;
      }
    }
    scanf("%d",&q);
    while (q--) {
      int l,r;
      scanf("%d %d",&l,&r);
      printf("%d
",ans[l][r]);
    }
  }
}