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

 

评论

1 楼 代码能力弱成渣 2012-12-08  

可以帮我看下我的代码么？我自己写的sam，也有ac过题的，但是最近跟别人讨论，说这个不是sam。
node *createnode(int l,node *fail)
{
    node *p=&memory[cnt];
    memory[cnt].len=l;
    memory[cnt].fail=fail;
    memset(memory[cnt++].next,NULL,sizeof(node *)*maxn);
    return p;
}

class SAM
{
    public:
    node *root;
    SAM()
    {
        root=NULL;
    }
    void Insert(char *str)
    {
        if(!root)
            root=createnode(0,NULL);
        node *loca=root;
        for(int i=0;str[i];i++)
        {
            int num=str[i]-'a';
            if(loca->next[num]==NULL)
                loca->next[num]=createnode(i+1,NULL);
            loca=loca->next[num];
        }
    }
    void Build()
    {
        std::queue<node *>s;
        while(!s.empty())
            s.pop();
        s.push(root);
        while(!s.empty())
        {
            node *loca=s.front();
            s.pop();
            for(int i=0;i<maxn;i++)
            {
                if(loca->next[i])
                {
                    if(loca==root)
                        loca->next[i]->fail=root;
                    else
                    {
                        node *tmp=loca->fail;
                        while(tmp)
                        {
                            if(tmp->next[i])
                                break;
                            tmp->next[i]=loca->next[i];
                            tmp=tmp->fail;
                        }
                        if(tmp==NULL)
                            loca->next[i]->fail=root;
                        else if(tmp->next[i]->len=tmp->len+1)
                        {
                            loca->next[i]->fail=tmp->next[i];
                        }
                        else
                        {
                            node *t=tmp->next[i];
                            node *nt=createnode(tmp->len+1,t->fail);
                            loca->next[i]->fail=t->fail=nt;
                            memcpy(nt->next,t->next,sizeof(node *)*maxn);
                            while(tmp&&tmp->next[i]==t)
                            {
                                tmp->next[i]=nt;
                                tmp=tmp->fail;
                            }
                        }
                    }
                    s.push(loca->next[i]);
                }
            }
        }
    }
};