折騰了好久。不過收獲還是很多的。第一次自己去畫SAM所建出來fail樹。深入體會了這棵樹的神奇性質。

當然，我最終靠著自己A掉了。（這是我第一次推SAM的性質（以前都是抄別人的，感覺自己好可恥），不過感覺好像是摸著黑行走啊！）

這道題，可以先對第一個串建出后綴自動機。然后第二個串在后綴自動機上跑。

首先,SAM所建出的fail樹的性質有：

1： 樹上一個節點對應了多個串，串的個數是 len[x] - len[fa[x]]， 同時它們都出現了 sz[x] 次（感覺好像說不大清，可以看一下代碼對于sz數組的處理）。

2： 設串的長度為 l 那么每個節點 x 的 sz[x] * (len[x] - len[fa[x]]) 的和為 （l+1) * l / 2

3: ? 樹上一個節點的所有后代所代表的串都是以這個節點代表的串為后綴的串。

4: ? 根據性質3推出： 如果一個字符串匹配到一個樹上的某個節點， 那么這個節點的所有祖先所代表的所有祖先都是它的子串，但那個節點本身所代表的所以串并不一定都是他的子串。

?

所以這道題的ans應該呼之欲出了。

（說了這么多，你們知道解題的思路是什么嗎？顯然對于子串的問題，我們肯定是假設當前匹配到第i個字符的時候，把以第i個字符結尾的所有字串都處理掉。）?

那么假設當前匹配到 i 字符時轉移到了節點x， 那么x對答案的貢獻就是 祖先所代表的所有的串（可以預處理）和 ?匹配到 i 字符時，(第二個串與第一個串的最長匹配長度-len[fa[x]]?)*sz[x]?

第二個串與第一個串的最長匹配長度-len[fa[x]]（這個就是第二個串在x節點內所能匹配的子串數）

?

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define rep(i,j,k) for(register int i = j; i <= k; i++)
 5 #define dow(i,j,k) for(register int i = j; i >= k; i--)
 6 #define ez(i,j) for(edge*i = head[j]; i; i=i->next)
 7 #define maxn 200005
 8 #define ll long long
 9 using namespace std;
10 
11 struct edge{ int to; edge*next; } e[maxn<<1], *pt = e, *head[maxn<<1];
12 inline void add(int x,int y) { pt->to = y, pt->next = head[x], head[x] = pt++; }
13 
14 int last = 1, u, v, nv, p, tot = 1, sz[maxn<<1], dep[maxn<<1], fa[maxn<<1], son[maxn<<1][26];
15 inline void extend(int c) {
16     u = last; p = last = ++tot; dep[p] = dep[u] + 1; sz[p] = 1;
17     while( u && !son[u][c] ) son[u][c] = p, u = fa[u];
18     if( !u ) fa[p] = 1;
19     else {
20         v = son[u][c];
21         if( dep[v] == dep[u] + 1 ) fa[p] = v;
22         else {
23             nv = ++tot; dep[nv] = dep[u] + 1;
24             fa[nv] = fa[v]; fa[v] = fa[p] = nv;
25             memcpy(son[nv],son[v],sizeof(son[v]));
26             while( son[u][c] == v ) son[u][c] = nv, u = fa[u]; 
27         }
28     } 
29 }
30 
31 int q[maxn<<1], tong[maxn<<1];
32 inline void pre() {
33     rep(i,1,tot) tong[dep[i]]++;
34     rep(i,1,tot) tong[i] += tong[i-1];
35     dow(i,tot,1) q[tong[dep[i]]--] = i;
36     int x;
37     dow(i,tot,1) x = q[i], sz[fa[x]] += sz[x];
38 
39 }
40 char c1[maxn]; ll dp[maxn<<1];
41 #define to i->to
42 inline void dfs(int x) {
43     dp[x] += 1ll * sz[x] * (dep[x] - dep[fa[x]]);
44     ez(i,x) dp[to] += dp[x], dfs(to);
45 }
46 
47 int main() {
48     scanf("%s", c1); int s1 = strlen(c1);
49     rep(i,0,s1-1) extend(c1[i]-'a');  
50     pre(); rep(i,1,tot) if( fa[i] ) add(fa[i],i); dfs(1);
51     //rep(i,1,tot) { rep(j,0,5) cout<<son[i][j]<<" "; cout<<endl; }
52     //rep(i,1,tot) cout<<sz[i]<<" "<<dp[i]<<" "<<dep[i]-dep[fa[i]]<<" "<<fa[i]<<endl;
53     scanf("%s", c1); s1 = strlen(c1);
54     int t, p = 1, l = 0; ll ans = 0;
55     rep(i,0,s1-1) {
56         t = c1[i] - 'a';
57         while( p && !son[p][t] ) p = fa[p];
58         if( !p ) p = 1, l = 0;
59         else l = min(l,dep[p]) + 1, p = son[p][t];
60         ans += dp[fa[p]], ans += 1ll * (l - dep[fa[p]]) * sz[p];
61     }
62     cout<<ans<<endl;
63     return 0;
64 }

?

轉載于:https://www.cnblogs.com/83131yyl/p/5483535.html

總結

以上是生活随笔為你收集整理的4566: [Haoi2016]找相同字符 SAM的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。