http://acm.hdu.edu.cn/showproblem.php?pid=5558
题意：
当前的位置是 i , 就找到 s1 = ( 以i为起点到 len 的连续串 ） ， s2=( 在 [0,i)内选一个起点到 len 的连续串) , 要求s1==s2 ; 如果有输出（ 最大的长度 ， 在[0,i)内选取的起点 ） ， 如果找不到就输出（-1 ，ASCLL(str[i]) )
分析：
利用SAM的联机特性 ， 一边插入一边找答案 ， 还要求最小的下标就多维护一个first_endpos
就是找到一个最大的某后缀 ， 比如：从起始状态不断的用当前字符str[i] , 往后面转移 ， 不断的p=trans[p][str[i]] , 就是说找到str[i]的最大后缀
#include <bits/stdc++.h> #define LL long long #define P pair<int, int> #define lowbit(x) (x & -x) #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, a, n) for (int i = a; i <= n; ++i) const int maxn = 1e6+550; #define mid ((l + r) >> 1) #define lc rt<<1 #define rc rt<<1|1 using namespace std; // __int128 read() { __int128 x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f;} // void print(__int128 x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) print(x / 10); putchar(x % 10 + '0');} int len; struct SAM{ int trans[maxn<<1][26], slink[maxn<<1], maxlen[maxn<<1]; // 用来求endpos int endpos[maxn<<1]; // 计算所有子串的和(0-9表示) int last, now, root; inline void newnode (int v) { maxlen[++now] = v; mem(trans[now],0); } inline void extend(int c,int i) { newnode(maxlen[last] + 1); int p = last, np = now; endpos[np]=i; // 更新trans while (p && !trans[p][c]) { trans[p][c] = np; p = slink[p]; } if (!p) slink[np] = root; else { int q = trans[p][c]; if (maxlen[p] + 1 != maxlen[q]) { // 将q点拆出nq，使得maxlen[p] + 1 == maxlen[q] newnode(maxlen[p] + 1); int nq = now; endpos[nq]=endpos[q]; memcpy(trans[nq], trans[q], sizeof(trans[q])); slink[nq] = slink[q]; slink[q] = slink[np] = nq; while (p && trans[p][c] == q) { trans[p][c] = nq; p = slink[p]; } }else slink[np] = q; } last = np; // 初始状态为可接受状态 } inline void init() { root = last = now = 1; slink[root]=0; mem(trans[root],0); //endpos[root]=0; } }sam; int main() { //printf("%d ",maxn); int t;scanf("%d",&t); for(int w=1 ; w<=t ; w++){ string T;cin>>T; sam.init(); len=T.size();printf("Case #%d: ",w); for(int i=0 ; i<len ; ) { int p=sam.root , k=0; while(i < len && sam.trans[p][T[i]-'a']) { p=sam.trans[p][T[i]-'a']; sam.extend(T[i]-'a',i); k++ , i++; } //printf("%d ",p); if(k) printf("%d %d ",k,sam.endpos[p]-k+1); else { sam.extend(T[i]-'a',i); printf("-1 %d ",(int)T[i]); i++; } } } //- sam.all(); }