题目大意：
求两个字符串的LCS。
思路：
对其中一个字符串构建SAM，然后用另一个字符串在里面匹配，按照SAM的边一直往下走，匹配到的连续的字符数就是公共字串的长度。
#include<string>
#include<cstring>
#include<iostream>
std::string s,t;
class SuffixAutomaton {
private:
static const int SIGMA_SIZE=;
int idx(const char ch) {
return ch-'a';
}
struct State {
State *link,*go[SIGMA_SIZE];
int len;
State(const int l) {
link=NULL;
len=l;
memset(go,,sizeof go);
}
};
State *root,*last;
void extend(const char ch) {
int w=idx(ch);
State *p=last;
State *new_p=new State(p->len+);
while(p!=NULL&&p->go[w]==NULL) {
p->go[w]=new_p;
p=p->link;
}
if(p==NULL) {
new_p->link=root;
} else {
State *q=p->go[w];
if(q->len==p->len+) {
new_p->link=q;
} else {
State *new_q=new State(p->len+);
memcpy(new_q->go,q->go,sizeof q->go);
new_q->link=q->link;
q->link=new_p->link=new_q;
while(p!=NULL&&p->go[w]==q) {
p->go[w]=new_q;
p=p->link;
}
}
}
last=new_p;
}
public:
void build(std::string &s) {
last=root=new State();
for(std::string::iterator i=s.begin();i<s.end();i++) extend(*i);
}
int match(std::string &s) {
int ret=,tmp=;
State *p=root;
for(std::string::iterator i=s.begin();i<s.end();i++) {
int w=idx(*i);
if(p!=NULL&&p->go[w]!=NULL) {
p=p->go[w];
tmp++;
} else {
while(p!=NULL&&p->go[w]==NULL) p=p->link;
if(p==NULL) {
p=root;
tmp=;
} else {
tmp=p->len+;
p=p->go[w];
}
}
ret=std::max(ret,tmp);
}
return ret;
}
};
SuffixAutomaton sam;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin>>s;
sam.build(s);
std::cin>>s;
std::cout<<sam.match(s)<<std::endl;
return ;
}