[洛谷]
多个串！1811的升级版~
其实做法很相似 我们只需要对第一个串建立SAM
然后 每个串在上面跑 由于是求所有字符串交的LCS
我们只需要记录每个节点与当前串匹配的max和之前所有串匹配的min
max是需要子树更新的 min要记得和当前的max还有len[节点最大长度]取min
然后这样就做完啦。
（才不会说我读的是所有字符串并的LCS 这个的做法可以直接跑一个然后扔进去一个就可以了qwq）
附代码。
#include#include #include #include #define inf 20021225#define ll long long#define mxn 100100using namespace std;struct edge{int to,lt;}e[mxn*4];struct node{int ch[26],fa,len,mx,mn;}t[mxn*4];int poi,lt,rt,in[mxn*4],cnt,n;char ch[mxn];void add(int x,int y){e[++cnt].to=y;e[cnt].lt=in[x];in[x]=cnt;}int id(char c){return c-'a';}void insert(int c){ int p=lt,np=lt=++poi; t[np].len=t[p].len+1; for(;p&&!t[p].ch[c];p=t[p].fa) t[p].ch[c]=np; if(!p){t[np].fa=rt;return;} int q=t[p].ch[c]; if(t[q].len==t[p].len+1){t[np].fa=q;return;} int nq=++poi; t[nq].len=t[p].len+1; memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch)); t[nq].fa=t[q].fa; t[q].fa=t[np].fa=nq; for(;p&&t[p].ch[c]==q;p=t[p].fa) t[p].ch[c]=nq;}void build(){for(int i=2;i<=poi;i++) add(t[i].fa,i);}void init(){for(int i=1;i<=poi;i++) t[i].mx=0;}void prework(){for(int i=1;i<=poi;i++) t[i].mn=inf;}void calc(){ int pos=rt,cur=0; for(int i=1;i<=n;i++) { int tmp=id(ch[i]); if(t[pos].ch[tmp]) cur++,pos=t[pos].ch[tmp]; else { for(;pos&&!t[pos].ch[tmp];pos=t[pos].fa); if(!pos) pos=rt,cur=0; else cur=t[pos].len+1,pos=t[pos].ch[tmp]; } t[pos].mx=max(t[pos].mx,cur); }}void dfs(int x){ for(int i=in[x];i;i=e[i].lt) { dfs(e[i].to); t[x].mx=max(t[x].mx,min(t[x].len,t[e[i].to].mx)); } t[x].mn=min(t[x].mn,t[x].mx);}int ans;void getans(){ for(int i=1;i<=poi;i++) ans=max(ans,t[i].mn);}int main(){ //freopen("in.txt","r",stdin); scanf("%s",ch+1);n=strlen(ch+1); rt=lt=++poi; for(int i=1;i<=n;i++) insert(id(ch[i])); build();prework(); while(~scanf("%s",ch+1)) { n=strlen(ch+1); init();calc();dfs(rt); } getans(); printf("%d\n",ans); return 0;}