记录编号	398355	评测结果	AAAAAAAAAA
题目名称	[SPOJ 705] 不同的子串	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.911 s
提交时间	2017-04-22 07:45:48	内存使用	2.67 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <deque>
#include <map>
#include <string>
template<class T, T &zero>  //zero是数组默认填充的内容。
class PersistableArray{  //可持久化数组
      //其实再准确点说，是对一段内存可持久化。
      //O(∩_∩)O 真是万能的方法呢？
        //（但是，不同的数据结构需要的额外的空间大概也是不同的呢）
        // 我们把数组可持久化，这样，用数组实现的数据结构，
        //                      应该就可以可持久化了。
  struct node{     //咦？这是啥
    node *ls, *rs;
    T value;
    node(){
      ls = rs = NULL; 
    }
  };
  std::vector<node *> roots;
  int left, right;
  node *build(int l, int r){  //线段树?
    if(l > r)return NULL;
    node *d = new node();
    if(l < r){
      int m = (l+r)>>1;
      d->ls = build(l, m), d->rs = build(m+1, r);
    }else if(l == r)d->value = zero;
    return d;
  }
  T query(node *d, int p, int L, int R){ //没错可持久化线段树
    if(!d)return zero;
    if(p == L && L == R)return d->value;
    int M = (L+R)>>1;
    if(p <= M)return query(d->ls, p, L, M);
    else if(p > M)return query(d->rs, p, M+1, R);
  }
  node *modify(node *d, int p, T val, int L, int R){ //我们不搞毒瘤
    if(!d)return d;                                  //我们只是脑洞的实现者。
    node *x = new node(); *x = *d;
    if(p == L && R == L)x->value = val;
    else{
      int M = (L+R)>>1;
      if(p <= M)x->ls = modify(d->ls, p, val, L, M);
      else if(p > M)x->rs = modify(d->rs, p, val, M+1, R);
    }
    return x;
  }
public:
  int version; //当前版本号
  void init(int start, int len){
    roots.push_back(NULL);
    left = start, right = start+len-1;
    roots.push_back(build(left, right));
    version = 1;
  }
  T query(int k, int p){ //查询版本k位置p上的值
    if(k > roots.size())return zero;
    if(p > right || p < left)return zero;
    return query(roots[k], p, left, right);
  }
  T query(int p){
    return query(version, p);
  }
  bool modify(int k, int p, T val, bool ct = true){ //ct 是否记录新版本
    if(k > roots.size())return false;  // 这个一定会产生新版本，
    if(p > right || p < left)return false; // ct只是表明要不要记录它。
    if(ct)roots.push_back(modify(roots[k], p, val, left, right));
    else roots[k] = modify(roots[k], p, val, left, right);
    return true;
  }
  bool modify(int p, T val, bool ct = false){ //这个modify默认不产生新版本
    bool f = modify(version, p, val, ct);
    if(f && ct)version += 1;
    return f;
  }
  T operator[](int id){return query(id);}
  void push(){ //产生一个当前版本的拷贝作为新版本，并改变当前版本号
    roots.push_back(roots[roots.size()-1]); 
    version += 1;
  }
};
class PersistableSuffixAutomata{
  //可持久化后缀自动机
  //把一般的后缀自动机用到的数组，用可持久化数组实现（这脑洞）
public:
  typedef std::map<int, int> trans;
  static int int_zero;
  static int int_one;
  PersistableArray<int, int_zero> len, link;
  PersistableArray<int, int_one> last, cnt;
  static trans empty_trans;
  PersistableArray<trans, empty_trans> next;
  PersistableSuffixAutomata(int rev){
    len.init(1, rev);
    link.init(1, rev);
    next.init(1, rev);
    last.init(1, 1); 
    cnt.init(1, 1);
  }
  void preview(){  //见 PersistableArray#push
    len.push();
    link.push();
    next.push();
    last.push();
    cnt.push();
  }
  void set_version(int ver){
    len.version = ver;
    link.version = ver;
    next.version = ver;
    last.version = ver;
    cnt.version = ver;
  }
  void extend(int c){
    preview();  //推♂倒旧版本
    int cur = cnt[1]+1; cnt.modify(1, cur);
    len.modify(cur, len[last[1]]+1);
    int p;
    for(p = last[1]; p && !next[p][c]; p = link[p]){
      trans t = next[p]; t[c] = cur;
      next.modify(p, t);
    }
    if(!p)link.modify(cur, 1);
    else{
      int q = next[p][c];
      if(len[q] == len[p]+1)link.modify(cur, q);
      else{
        int clone = cnt[1]+1; cnt.modify(1, clone);
        link.modify(clone, link[q]);
        len.modify(clone, len[p]+1);
        next.modify(clone, next[q]);
        for(; p && next[p][c] == q; p = link[p]){
          trans t = next[p]; t[c] = clone;
          next.modify(p, t);
        }
        link.modify(cur, clone);
        link.modify(q, clone);
      }
    }
    last.modify(1, cur);
  }
};
int PersistableSuffixAutomata::int_zero = 0;
int PersistableSuffixAutomata::int_one = 1;
std::map<int, int> PersistableSuffixAutomata::empty_trans = std::map<int, int>();
//真是不优美，c++98并不滋瓷右值引用，现在这个实现方式真是难看。。。

PersistableSuffixAutomata sam(1e5+10);
char str[50002];
int main(){
  freopen("subst1.in", "r", stdin);
  freopen("subst1.out", "w", stdout);
  scanf("%s", str);
  int ans = 0;
  for(int i = 0; str[i]; i++){
    sam.extend(str[i]-'A');
    ans += sam.len[sam.last[1]]-sam.len[sam.link[sam.last[1]]];
  }
  printf("%d\n", ans);
  return 0;
}