acwing 2811. 最长公共子串(SAM)

我们可以很好的利用SAM的性质
如果我们跑到一个节点
那么这个节点的所有连续后缀一定能跑到
我们每次去掉一个字符 显然如果endpos相同的话 直接可以跳过
所以我们直接跑 后缀链接树 恰好删掉一个字符 如果可以继续匹配
我们就让长度加一
所以我们就需要遍历每一个状态
但是我们考虑到一个信息会丢失的问题
我们每次 需要将 某个串的信息 传递到 他的 后缀链接树的父亲节点
至此就结束了

但是我想了一个不理解的问题
为什么 dp[u]=max(dp[v],dp[u])
这样这个结点处理的 信息可以会大于 所能表示的最长串
（所以很纠结 如果有会的大佬可以私我
如果只有两个串是可以不用的

呸呸呸 我知道为啥了 因为ans初始化的时候就是 这个节点所代表的最长串
如果大于 最长串的话 每一轮的最后还是会取min

所以才不影响正确性

其实数据范围大一点还可以 继续做优化
可以跑出 最短串的SAM
然后就是不要用memset

#include 
using namespace  std;
//#define  int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define pb  push_back
#define inf 1ll<<62
#define endl "\n"
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define de_bug(x) cerr << #x << "=" << x << endl
#define all(a) a.begin(),a.end()
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--)
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int n, m , k;
string  s;
string  t;
struct node {
	int len, fa;
	int son[26];
} tr[N * 2];
int cnt = 1;
int last = 1;
int f[N * 2];
void extend (int c) {
	int p = last, np = last = ++cnt;
	f[cnt] = 1;
	tr[np].len = tr[p].len + 1;
	for(; p && !tr[p].son[c];  p = tr[p].fa) tr[p].son[c] = np;
	if(!p) tr[np].fa = 1;
	else {
		int q = tr[p].son[c];
		if(tr[q].len == tr[p].len + 1)tr[np].fa = q;
		else {
			int nq = ++cnt;
			tr[nq] = tr[q];
			tr[nq].len = tr[p].len + 1;
			tr[q].fa = tr[np].fa = nq;
			for(; p && tr[p].son[c] == q; p = tr[p].fa) tr[p].son[c] = nq;
		}
	}
}
int dp[N];
vi g[N];
int ans[N];
void dfs(int u) {
	for(auto v : g[u]) {
		dfs(v);
		dp[u] = max(dp[u], min(dp[v], tr[u].len) ) ;
	}
}
void solve() {
	cin >> n;
	cin >> t;
	for(auto c : t)extend(c - 'a');
	for(int i = 1; i <= cnt; i++) {
		ans[i] = tr[i].len;
	}
	for(int i = 2; i <= cnt; i++) {
		g[tr[i].fa].push_back(i);
	}

	for(int i = 1; i <= n - 1; i++) {
		cin >> s;
		int p = 1;
		int maxlen = 0;
		memset(dp, 0, sizeof(dp));
		for(auto c : s ) {
			while(p > 1 && !tr[p].son[c - 'a']) p = tr[p].fa, maxlen = tr[p].len ;
			if(tr[p].son[c - 'a'])p = tr[p].son[c - 'a'], maxlen++;
			dp[p] = max(dp[p], maxlen);
		}
		dfs(1);
		for(int j = 1; j <= cnt; j++) {
			ans[j] = min(ans[j], dp[j]);
		}
	}
	int ma = -1;
	for(int i = 1; i <= cnt; i++) {
		ma = max(ma, ans[i]);
	}
	cout << ma << endl;
}
int  main() {
	IOS;
	int _ = 1;
	//cin>>_;
	while( _-- )
		solve();
}
/*
3
dacbac
dac
bac
*/
    
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106