hdu_1403_SAM_求最小公共字首

題目： click here

就是求最小公共字首

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_NODES = 3555555;
const int N = 1111111;
struct node{
	struct node *ch[26];
	struct node *f;
	int mx;
	void init(){
		memset(ch,0,sizeof(ch));
		f = 0;
	}
}*root,*cnt,*tail,pool[MAX_NODES];
char s[N],ts[N];
int n;
void insert(int c,int len){
	node *p = tail, *np = cnt++;
	for( ; p && !p->ch[c] ; p = p->f) p->ch[c] = np;
	np->mx = len;
	tail = np;
	if(!p) np->f = root;
	else 
		if( p->ch[c]->mx == p->mx+1) np->f = p->ch[c];
		else{
			node *q = p->ch[c], *r = cnt++;
			*r = *q;
			r->mx = p->mx+1;
			q->f = np->f = r;
			for( ; p && p->ch[c] == q ; p = p->f) p->ch[c] = r; 
		}
}
void init_suffix_auto(char s[]){
	int len = 0;
	tail = cnt = root = pool; cnt++ , root->init();
	for(int i = 0;i < (n<<1) ;i++)
		pool[i].init();
	for( ; s[len] ; len++){
		insert(s[len] - 'a', len+1);
	}
}

int main(){
	int t;
	while(scanf("%s",s)!=EOF){
		scanf("%s",ts);
		n = strlen(s);
		init_suffix_auto(s);
		node *p=root;
		int ans = 0,tmp=0;
		for(int i = 0; ts[i]; i++){
			int id = ts[i]-'a';
			if(p->ch[id]){
				p = p->ch[id];
				tmp++;
			}else{
				for(; p && !p->ch[id]; p = p->f) 
					;
				if(!p){
					p = root;
					tmp = 0;
				}else{
					tmp = p->mx+1;
					p = p->ch[id];
				}
			}
			ans = max(tmp,ans);
		}
		printf("%d\n",ans);
	}
	return 0;
}