求两个字符串的最长公共连续子序列(SAM实现)

//时间复杂度O(N)#include <stdio.h>#include <cstring>const int R = 26;const int N = 250005; //字符串的长度struct node{node *next[R], *par; int v; //该节点表示的子串的最大长度,最小长度即为par的最大长度+1,因此可以不用存下来}nodes[N*2+100], *root;int cnt;  //树中节点个数node* newNode(int v, node* par){nodes[cnt].v = v; nodes[cnt].par = par; memset(nodes[cnt].next, 0, sizeof(node*)*R); return &nodes[cnt++]; }inline int id(char ch){return ch-'a'; }//构造后缀自动机void SAM(char* str, node*& root){cnt = 0; node *last, *now, *np; last = root = newNode(0, NULL);int i, k; for(i = 0; str[i]; i++){now = last; k = id(str[i]); np = newNode(i+1, NULL); while(now && ! now->next[k]){now->next[k] = np; now = now->par; }if(!now){np->par = root; }else if(now->next[k]->v == now->v+1){np->par = now->next[k]; }else{node* t = now->next[k]; node* nt = newNode(now->v+1, t->par); t->par = np->par = nt; memcpy(nt->next, t->next, sizeof(node*)*R); while(now && now->next[k] == t){now->next[k] = nt; now = now->par;}}last = np; }}inline void upMax(int& a, int tmp){if(a < tmp) a = tmp;}//求字符串sa和sb的最长公共连续子序列int maxCommonLen(char* sa, char* sb){cnt = 0; SAM(sa, root); //test(); node *now;now=root;int i, k, ans, len;ans = len = 0; for(i = 0; sb[i]; i++){k = id(sb[i]); if(now->next[k]){len++; now = now->next[k];}else{while(now && ! now->next[k]){now = now->par; }if(now){len = now->v + 1; now = now->next[k]; }else{now = root; len = 0; }}upMax(ans, len); }return ans; }