F09 后缀自动机(SAM)

【详细注释 | 字符串算法集合 2】后缀自动机 SAM & 后缀数组 SA-CSDN博客

#include <iostream>
#include<bits/stdc++.h> 
using namespace std;
 
typedef long long LL;
const int N = 2e6 + 10;    // 开两倍，表示后缀链接树最大节点数量 
char s[N];     
vector<int> G[N];      // 邻接表，用于构建后缀链接树
LL cnt[N], ans;       // cnt[i] 表示状态 i 对应的子串出现次数，ans 是最终答案
int tot, np;       // tot 是总节点数（初始为 1，因为状态 1 是根节点），np 是当前节点 / 上一个节点  
// 注意这里的 np 只会指向通过下标添加的节点，也就是上一个 np 一定是当前文本串下标前一个字符为结尾的节点
// （看到后面就懂了） 
 
int len[N];        // len[i] 表示节点 i 的最长子串长度
int fa[N], ch[N][26];
/*
再来回顾下这俩数组的特性：
fa[p] 的最长串就是 p 包含子串的最长共同后缀
（当然 fa[p] 的其它串也是 p 子串的后缀就是了） 
 
ch[i][c] 是节点 i 通过字符 c 的转移到的点
可能有多个 i 的 ch[i][c] 指向同一个节点
而这个节点所包含的子串正是这些 i 的子串后面接上 c
*/  
 
void extend(int c) {
    int p = np;            // p 指向上一个 np（当前下标 - 1 位置的节点） 
    tot ++; 
    np = tot;                  // 给新节点新编号 
    len[np] = len[p] + 1;     // 新状态的最长子串长度为旧状态 + 1
    cnt[np] = 1;              // 新创建的子串出现次数初始化为 1
    
    // 从当前状态 p 开始，沿着后缀链接不断回跳，直到遇到已经存在 c 转移的状态或到达根节点
    for (; p && !ch[p][c]; p = fa[p]) {
        ch[p][c] = np; 
    }
    // 因为 fa[p] 一条链上的节点后缀都与 p 相同，而点 p 又是 np 的前一个下标的点
    // 所以这一条链上的点所包含的子串后面接上当前字符 c，都是合法的以当前字符结尾的子串
	// 满足 ch 的定义 （一个节点可能包含不止一个子串，也是因为这句话
	// 因为有多个 p 指向 np，自然转移到 np 的字符串数量也就不止一个） 
    
    if (p == 0) {
        fa[np] = 1;   // p 回跳到 0（根节点的 fa），说明 c 是新字符，从新点向根节点建后缀链接
        // 也就是树上没有节点和 np 有共同后缀 
    } 
	else {    // p 没有回跳到 0，说明 c 是旧字符
	// 此时的 p 是一开始的 p 的祖先（后缀），也是离最开始的 p 最近的一个能通过 c 转移的 
        
        int r = ch[p][c];      // r 是 p 通过 c 转移到的状态（r 的结尾字符也是 c ） 
        
        // 若 len[r] == len[p] + 1，说明 r 状态恰好是 p 通过 c 转移得到的状态
        if (len[r] == len[p] + 1) {
            fa[np] = r;         
		// 因为现在 p 的后缀和最开始的 p（当前下标 - 1 位置的节点）一样，而通过 p 转移来的 r 结尾字符也是 c 
			// 满足条件的同时 p 离最开始的 p 最近（共同后缀最长） 
			// 所以 r 和 np 有最长共同后缀，可以建立后缀链接 
        } 
        
        /*
          若 len[r] != len[p] + 1，说明 r 状态包含了比 p 通过 c 转移得到的更长的字串 
          而我们只需要 p 通过 c 转移得到的字符串，这时候我们分裂 r
          这种情况是怎么发生的呢？就是之前我们把 fa[p] 一条链的 ch 都指向一个点
		  这条链上的 len 肯定是递减的，会出现 len[ch[p][c]] != len[p] + 1 的情况 
		
		  那为啥要分裂 r 呢？
		  比如说之前出现过 aab，我们就把 ch[a][ b ] 和 ch[aa][ b ] 都指向了 b 代表的节点
		  现在我们要用到 ab，但是没有 ab 这个节点，只能通过分裂 aab 得到它 
		  当然之前指向时一个个更新是不现实的，所以等我们现在用到了再更新 
		 */
        else {
        	tot ++;
            int nr = tot;            // 创建新状态 nr
            len[nr] = len[p] + 1;    // nr 的最长子串长度为 len[p] + 1
            // 发现这里没有 cnt[nr] = 1
			// 因为 nr 是从 r 分裂而来的，后面算答案不能算上 nr
			// ************很重要上面这一点！！！ 
            fa[nr] = fa[r];   // nr 继承 r 的后缀链接
			// r 和 np 的后缀链接都指向 nr
            fa[r] = nr; 
            fa[np] = nr;
            /*
              为啥可以这么做呢？ 
              已知 nr 是通过 p 转移过来的，设 r 通过 pp 直接转移过来
              （最然现在的 r = ch[p][c]，但很明显 r 不是 p 的直接转移对象（len[r] > len[p] + 1）） 
              （那我们就假设存在 pp，r = ch[pp][c] && len[r] = len[pp] + 1） 
			  其中 p 在后缀链接树上是 pp 的祖先，可以简单理解成 fa[pp] = p
			  也就是 p 是 pp 的后缀，所以 nr 是 r 的后缀，是 r 的祖先
			  但同时 nr 又是以 p 为后缀（不包含 c），以字符 c 结尾分支的最顶端（这个自己想下或者看下面的反例）
			  也就是 r 后缀链接的 fa 的子串不可能比 nr 长  
			  
			  举一个反例：
			  r = aaab，fa[r] = aab，nr = ab
			  看上去不合法，但是如果存在 aab 的话，r 早就指向 aab 了 
			  
			  至于 r 和 np 的后缀链接都指向 nr，因为 nr 是 r 的最近祖先
			  而对于通过最开始的 p 转移过来的 np，现在 p 转移过来的 nr 是它的后缀
            */
            
            // 将所有通过 c 转移到 r 的状态改为转移到 nr
            // 从 p 开始沿着后缀链接回跳，将所有通过 c 转移到 r 的状态改为转移到 nr
            // 虽然也不一定 len[p] + 1 = len[nr]，但好歹 nr 的 len 比 len[r] 小 
            for (; p && ch[p][c] == r; p = fa[p]) {
                ch[p][c] = nr;
            }
            
            // nr 继承 r 的所有转移边
            memcpy(ch[nr], ch[r], sizeof(ch[r]));
            // 和前面那个 for 一条链 fa 的一个道理，不必再深究 
        }
    }
}
 
void dfs(int x) { 
    // 遍历当前节点的所有子节点（后缀链接树中的子节点）
    for (auto y : G[x]) {
        dfs(y);         
        cnt[x] += cnt[y];      // 子节点的出现次数累加到父节点
		// 因为父节点是子节点的后缀，所以子节点出现父节点也一定出现 
    }
    
    // 如果该状态对应的子串出现次数大于 1，则更新答案
    if (cnt[x] > 1) {
        ans = max(ans, cnt[x] * len[x]); 
    }
    // 为啥只在意最长串的 len 呢？
	// 因为后缀链接树的结构也保证了节点其它的串，不可能通过累加的方式得出最长串
	//（也就是最长串不是该节点其他串的回文） 
	//所以最长串才是最优的 
	
	// 那这样做法的正确性怎么证明（不重复不遗漏）？
	// 首先，每个节点的最长串都不重复
	// 然后，每个节点的最长串都是该节点长度最长的 
	// 最后，一个节点的最长串就算是另一个节点最长串的后缀，但它们的结束位置也不同 
	// （因为我们上面分裂节点的 cnt 为 0） 
	// （这里意会吧我尽力了） 
}
 
int main() {
	ios::sync_with_stdio(False);
	cin.tie(0);
	
	cin >> s + 1;
    
    tot = np = 1;
    fa[1] = 0;
    memset(cnt, 0, sizeof(cnt));
    memset(ch, 0, sizeof(ch));
    memset(len, 0, sizeof(len)); 
    
    for (int i = 1; s[i]; i++) {
        extend(s[i] - 'a');      // 按文本串下标顺序插入节点s
    }
    
    for (int i = 2; i <= tot; i++) {    // 构建后缀链接树，每个点的最长公共后缀连到自己 
        G[fa[i]].push_back(i);    // 就是那个图中绿色箭头反过来连 
    }
    
    ans = 0;     // 答案初始化
    dfs(1);
    
    cout << ans << "\n";     // 输出答案最大的（子串出现次数 x 子串长度） 
    
    return 0;
}