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

求两个字符串的最长公共连续子序列(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; 
}