SPOJ LCS2 Longest Common Substring 2[后缀自动机+dp]

题意:

求n个串的最长公共子串,n<=10

思路:

不会啊orz

先放一波参考资料&题解好了。

codeforces_Understanding Suffix Automaton in depth

code风景区_spoj_lcs2

code风景区_sam教学

candy SPOJ 1812 LCS2 [后缀自动机 DP]

首先参考下2个串的LCS的做法spoj-lcs

卧槽终于懂了...

一个串在上面走的时候记录与每个状态公共子串的最大值,注意**出现次数向父亲传递**,一个状态能到达说明了Suffix Link指向的状态可以取到最大子串,这一步对val后基数排序然后倒着更新就行了

...代码之后补

关键是理解这句话:一个状态能到达说明了Suffix Link指向的状态可以取到最大子串

比如如果状态S(从初始状态到S状态所表示的子串是abcbc) 能够最长向前匹配的长度是x,那么状态s的par的状态Q(从初始状态到Q状态所表示的子串是bc)也至少为x.

所以dp[link[v]] = Max{dp[link[v]],dp[v]}

妈个鸡。。。

没事改什么字符集大小啊。。。

上道题做的是数字。。就手贱把字符集的大小改成了12.。。忘了改回来。。WA到死。。。

/* ***********************************************
Author :111qqz
Created Time :2017年11月08日 星期三 18时50分18秒
File Name :4436.cpp
************************************************ */
 1#include <bits/stdc++.h>
 2#define PB push_back
 3#define fst first
 4#define sec second
 5#define lson l,m,rt<<1
 6#define rson m+1,r,rt<<1|1
 7#define ms(a,x) memset(a,x,sizeof(a))
 8typedef long long LL;
 9#define pi pair < int ,int >
10#define MP make_pair
 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6#define MAXALP 30
 7const int mod = 2012;
 8struct state
 9{
10    int len, link, nxt[MAXALP];
11};
12const int N =1E5+7;
13state st[N*2];
14int sz, last,rt;
15char s[N];
16int cnt[2*N],rk[2*N];//for radix sort
17int dp[2*N],maxlen[2*N];
18void sa_init()
19{
20    sz = 0;
21    last = rt = ++sz;
22    st[1].len = 0;
23    st[1].link=-1;
24    ms(st[1].nxt,-1);
25}
26void sa_extend(int c)
27{
28    int cur = ++sz;
29    st[cur].len = st[last].len + 1;
30    memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
31    int p;
32    for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
33        st[p].nxt[c] = cur;
34    if (p == -1) {
35        st[cur].link = rt;
36    } else {
37        int q = st[p].nxt[c];
38        if (st[p].len + 1 == st[q].len) {
39            st[cur].link = q;
40        } else {
41            int clone = ++sz ;
42            st[clone].len = st[p].len + 1;
43            st[clone].link = st[q].link;
44            memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
45            for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
46                st[p].nxt[c] = clone;
47            st[q].link = st[cur].link = clone;
48        }
49    }
50    last = cur;
51}
52void topo()
53{
54    ms(cnt,0); 
55    for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
56    for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
57    for (int i = 1 ; i <= sz  ;i++) rk[cnt[st[i].len]--] = i;
58}
59char ST[N];
60int main()
61{
62#ifndef  ONLINE_JUDGE 
63        freopen("./in.txt","r",stdin);
64#endif
 1    int flag = 1;
 2    ms(maxlen,0x3f);
 3    while (scanf("%s",ST)!=EOF)
 4    {
 5//  cout<<"ST:"<<ST<<endl;
 6    if (flag)
 7    {
 8        sa_init();
 9        for (int i = 0,len = strlen(ST);  i < len ; i++)
10        {
11        sa_extend(ST[i]-'a');
12        }
13        topo();
14        flag = 0 ;
15    }
16    else
17    {
18        ms(dp,0);
19        int now = rt,len = 0;
20        for ( int i = 0,_len = strlen(ST) ; i < _len ; i++)
21        {
22        if (st[now].nxt[ST[i]-'a']!=-1)
23        {
24            now = st[now].nxt[ST[i]-'a'];
25            len++;
26            dp[now] = max(dp[now],len);
27          //  printf("now:%d dp[now]:%d len: %d\n",now,dp[now],len);
28        }
29        else 
30        {
31            while (now!=-1&&st[now].nxt[ST[i]-'a']==-1) now = st[now].link;
32            if (now==-1) now=rt,len=0;else len = st[now].len + 1,now=st[now].nxt[ST[i]-'a'],dp[now] = max(dp[now],len);
33        }
34        }
35        for ( int i = sz ; i >= 1 ; i-- )
36        {
37        int v = rk[i];
38        st[v].len = min(st[v].len,dp[v]);
39        dp[st[v].link] = max(dp[st[v].link],dp[v]);
40//      dp[v] = 0 ;  //其实只是为了清空,多次ms太慢了...
41        }
42    }
    }
1    int ans = 0 ;
2    for ( int i = 1 ; i <= sz ; i++) ans = max(ans,st[i].len);
3    printf("%d\n",ans);
4//  cout<<ans<<endl;
1#ifndef ONLINE_JUDGE  
2    fclose(stdin);
3#endif
4    return 0;
5}