[USACO17DEC] Standing Out from the Herd P

admin LV 10 SU @ 2026-5-7 23:33:00

广义 SAM 板子题。

思路

首先对所有串建广义 SAM。

本题和模版唯一不同的一点就是，模版是统计总共有多少子串，多个相同串虽然不算，但是起码算一个，而这题是一个都不算。。。

考虑在 parent 树上染色。

做法：

建广义 SAM。
对于每个字符串，往上跳 father 指针。

如果 parent 树当前节点已经染过其他颜色了，因为多个相同串一个都不算，那么就把它设为不可用。

否则，将该节点染色为当前字符串编号。

最后统计答案的时候，直接按照染上的颜色统计即可。

如果当前颜色不可用，那就不管。否则把对应颜色的答案加上子串数量。

如果你不知道怎么求子串数量，~~说明你根本不会用 SAM~~，请参考 P2408 和 P6139。

还是很简单的。

具体实现（update 即染色函数）：

inline void update(int x, int id)
{
    while (~x && ~num[x] && num[x] != id)
    {
        num[x] = num[x] ? -1 : id;
        x = fa[x];
    }
}
inline void solve()
{
    int p = 0;
    for (int i = 1; i <= n; i++, p = 0)
        for (char c : s[i])
            update(p = t[p][c - 'a'], i);
    for (int i = 0; i <= tot; i++)
        if (~num[i] && ~fa[i])
            ans[num[i]] += len[i] - len[fa[i]];
    for (int i = 1; i <= n; i++)
        cout << ans[i] << '\n';
}

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
string s[N];
int n;
struct SAM
{
    int tot, last, fa[N << 1], len[N << 1], t[N << 1][26];
    int num[N << 1], ans[N << 1];
    inline SAM()
    {
        tot = last = 0;
        fa[0] = -1;
    }
    inline void insert(char c)
    {
        c -= 'a';
        int cur = ++tot;
        len[cur] = len[last] + 1;
        int p = last;
        last = cur;
        while (~p && !t[p][c])
            t[p][c] = cur, p = fa[p];
        if (!~p)
        {
            fa[cur] = 0;
            return;
        }
        int x = t[p][c];
        if (len[p] + 1 == len[x])
            fa[cur] = x;
        else
        {
            len[++tot] = len[p] + 1;
            fa[tot] = fa[x];
            memcpy(t[tot], t[x], sizeof(t[x]));
            while (~p && t[p][c] == x)
                t[p][c] = tot, p = fa[p];
            fa[x] = fa[cur] = tot;
        }
    }
    inline void update(int x, int id)
    {
        while (~x && ~num[x] && num[x] != id)
        {
            num[x] = num[x] ? -1 : id;
            x = fa[x];
        }
    }
    inline void solve()
    {
        int p = 0;
        for (int i = 1; i <= n; i++, p = 0)
            for (char c : s[i])
                update(p = t[p][c - 'a'], i);
        for (int i = 0; i <= tot; i++)
            if (~num[i] && ~fa[i])
                ans[num[i]] += len[i] - len[fa[i]];
        for (int i = 1; i <= n; i++)
            cout << ans[i] << '\n';
    }
} sam;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        sam.last = 0;
        for (char c : s[i])
            sam.insert(c);
    }
    sam.solve();
    return 0;
}

huangzheng LV 6 SU @ 2025-10-8 17:12:31

后缀数组 SA 做法题解 SA 做法代码：

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 4e5 + 10;
 
char ss[N];
int n, m;
LL ed[N];
int c[N], x[N], y[N], sa[N];
int s[N];   // 这里一定要用 int ！！ 
 
void get_sa() {
	int i, j, k;
	memset(c, 0, sizeof(c));
	
	for (i = 1; i <= n; i ++) {
		c[x[i] = s[i]]  ++;
	}
	for (i = 1; i <= m; i ++) {
		c[i] += c[i - 1];
	}
	for (i = n; i >= 1; i --) {
		sa[c[x[i]]] = i;
		c[x[i]] --;
	}
	
	for (k = 1; k <= n; k <<= 1) {
		for (i = 1; i <= m; i ++) {
			c[i] = 0;
		}
		for (i = 1; i <= n; i ++) {
			y[i] = sa[i];
		}
		for (i = 1; i <= n; i ++) {
			c[x[y[i] + k]] ++;
		}
		for (i = 1; i <= m; i ++) {
			c[i] += c[i - 1];
		}
		for (i = n; i >= 1; i --) {
			sa[c[x[y[i] + k]]] = y[i];
			c[x[y[i] + k]] --;
		}
		
		for (i = 1; i <= m; i ++) {
			c[i] = 0;
		}
		for (i = 1; i <= n; i ++) {
			y[i] = sa[i];
		}
		for (i = 1; i <= n; i ++) {
			c[x[y[i]]] ++;
		}
		for (i = 1; i <= m; i ++) {
			c[i] += c[i - 1];
		}
		for (i = n; i >= 1; i --) {
			sa[c[x[y[i]]]] = y[i];
			c[x[y[i]]] --;
		}
		
		for (i = 1; i <= n; i ++) {
			y[i] = x[i];
		}
		for (m = 0, i = 1; i <= n; i ++) {
			if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) {
				x[sa[i]] = m;
			}
			else {
				m ++;
				x[sa[i]] = m;
			}
		}
		
		if (m == n) {
			break;
		}
	}
}
 
int height[N], rk[N];
int mp[N];
LL ans[N];
 
void get_height() {
	int i, j, k;
	memset(height, 0, sizeof(height));
	
	for (i = 1; i <= n; i ++) {
		rk[sa[i]] = i;
	}
	for (k = 0, i = 1; i <= n; i ++) {
		if (rk[i] == 1) {
			continue;
		}
		
		if (k) {
			k --;
		}
		
		int j = sa[rk[i] - 1];
		while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) {
			k ++;
		}
		height[rk[i]] = k;
	}
}
 
int main () {
	ios::sync_with_stdio(False);
	cin.tie(0);
	
	int T;
	cin >> T;
	n = 0; 
	for (int i = 1; i <= T; i ++) {
		cin >> ss + 1;
		for (int j = 1; ss[j]; j ++) {
			n ++;
			s[n] = ss[j] - 'a';    // 这里一定要 - 'a'！！！不然会爆 long long 
			mp[n] = i;
		}
		ed[i] = n;
		n ++;
		m = s[n] = 26 + i;   // 间隔符：别管是啥妖魔鬼怪不一样就行，同时更新上限 m 
		// 只要字典序不插在中间干扰答案就行 
	}
	
	get_sa();
	get_height();
	
	LL mn = 0;
	// mn：从上一个不同字符串的字典序相邻后缀到当前后缀的 LCP 最小值 
	memset(ans, 0, sizeof(ans));
	for (int i = 1; i <= n; i ++) {
		LL L = height[i];
		mn = min(L, mn); 
		int mx = mp[sa[i]], my = mp[sa[i - 1]];
		if (mx == my) {   // 相邻俩后缀属于一个字符串 
			ans[mx] += ed[mx] - sa[i] + 1 - L;
			// 字符串 mx 加上自己以 sa[i] 为开头的剩下的不重复子串
			// 比如说从 sa[i] 到字符串结尾还剩 abc，height 为 2
			// 那么从 a 开始有 3（字符串剩下长度）个后缀：a，ab，abc
			// 再减掉 2（a 和 ab），就是不重复子串 
		}
		else {
			ans[mx] += ed[mx] - sa[i] + 1 - L;
			// 和前面那个一样，都是 mx 自身的答案贡献 
			ans[my] += mn - L;
			/* *** 难点
			 假设上一个不同字符串到当前的子串分别是：
			 ba，bb，bbb，bbbb，bbbc
			 除了中间三个全是 b 的所属同一个字符串 s，其他头尾两个都是不同的 
			 mn = 1，字符串 s 的答案贡献在 i = bb 时减了 b 
			 在 i = bbb 减了 b 和 bb 
			 在 i = bbbb 时减了 b 和 bb 和 bbb
			 在 i = bbbc 时减了 b 和 bb 和 bbb
			 我们发现同一个 b 的贡献在和别的字符串匹配时减了 2 次
			 但实际上 bbbb 字符串减 b 的贡献只用减 1 次
			 （本来要减 4 次，但剩下的 b 在 mx = my 时把自身重复的都减掉了） 
			 （我们这里只讨论 bbbb 在减掉自身相重复的子串后，与外界相重复的子串应该怎么减）
			 而 b 这个子串与其它两个字符串的后缀相重复，在 bbbb 内的贡献减 1 次就好
			 所以还要将 mn 加回来 
			 */
			mn = L;   // 更新 mn 
		}
	}
	
	for (int i = 1; i <= T; i ++) {
		cout << ans[i] << "\n";
	}
	
	return 0;
}

后缀自动机 SAM 做法题解 SAM 做法代码：

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 2e5 + 10;
 
char s[N], ss[N];
int np, tot;
int len[N], v[N], slen[N];
int ch[N][30], fa[N];
LL ans[N];
 
void extend(int c) {
	int p = np;
	tot ++;
	np = tot;
	len[np] = len[p] + 1;
	
	for (; p && !ch[p][c]; p = fa[p]) {
		ch[p][c] = np;
	}
	
	if (!p) {
		fa[np] = 1;
	}
	else {
		int r = ch[p][c];
		
		if (len[r] == len[p] + 1) {
			fa[np] = r;
		}
		else {
			tot ++;
			int nr = tot;
			len[nr] = len[p] + 1;
			
			fa[nr] = fa[r];
			fa[r] = nr;
			fa[np] = nr;
			
			for (; p && ch[p][c] == r; p = fa[p]) {
				ch[p][c] = nr;
			} 
			memcpy(ch[nr], ch[r], sizeof(ch[r]));
		}
	}
} 
 
void get_v(int x, int i) {
	for (; x && v[x] != i && v[x] != -1; x = fa[x]) {   
	// 遇到 v[x] 不是当前字符串，那么 x 的后缀也不是当前字符串，直接退出就好 
		if (v[x] != 0) {
			v[x] = -1;
		}
		else {
			v[x] = i;
		}
	}
}
 
int main () {
	ios::sync_with_stdio(False);
	cin.tie(0);
	
	tot = np = 1;
	fa[1] = 0;
	memset(len, 0, sizeof(len));
	memset(v, 0, sizeof(v));
	memset(ch, 0, sizeof(ch));
	
	int n, sl = 0;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		np = 1;
		cin >> ss + 1;
		slen[i] = strlen(ss + 1);
		for (int j = 1; ss[j]; j ++) {   // 神人出题人，搞得读入像坨 
			s[sl + j] = ss[j];
			extend(ss[j] - 'a');
		}
		sl += slen[i];
	}
	
	int x = 1, last = 0;
	for (int i = 1; i <= n; i ++) {
		x = 1;
		for (int j = 1; j <= slen[i]; j ++) {
			x = ch[x][s[last + j] - 'a'];
			get_v(x, i);
		}
		last += slen[i];
	}
	
	memset(ans, 0, sizeof(ans));
	
	for (int i = 1; i <= tot; i ++) if (v[i] != -1) {
		ans[v[i]] += (len[i] - len[fa[i]]);
	}
	
	for (int i = 1; i <= n; i ++) {
		cout << ans[i] << "\n";
	}
	
	return 0;
}

huangzheng LV 6 SU @ 2025-10-8 17:12:13

后缀数组 SA 做法题解

SA 做法代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4e5 + 10;
char ss[N];
int n, m;
LL ed[N];
int c[N], x[N], y[N], sa[N];
int s[N];   // 这里一定要用 int ！！
void get_sa() {
int i, j, k;
memset(c, 0, sizeof(c));
for (i = 1; i &lt;= n; i ++) {
	c[x[i] = s[i]]  ++;
}
for (i = 1; i &lt;= m; i ++) {
	c[i] += c[i - 1];
}
for (i = n; i &gt;= 1; i --) {
	sa[c[x[i]]] = i;
	c[x[i]] --;
}

for (k = 1; k &lt;= n; k &lt;&lt;= 1) {
	for (i = 1; i &lt;= m; i ++) {
		c[i] = 0;
	}
	for (i = 1; i &lt;= n; i ++) {
		y[i] = sa[i];
	}
	for (i = 1; i &lt;= n; i ++) {
		c[x[y[i] + k]] ++;
	}
	for (i = 1; i &lt;= m; i ++) {
		c[i] += c[i - 1];
	}
	for (i = n; i &gt;= 1; i --) {
		sa[c[x[y[i] + k]]] = y[i];
		c[x[y[i] + k]] --;
	}
	
	for (i = 1; i &lt;= m; i ++) {
		c[i] = 0;
	}
	for (i = 1; i &lt;= n; i ++) {
		y[i] = sa[i];
	}
	for (i = 1; i &lt;= n; i ++) {
		c[x[y[i]]] ++;
	}
	for (i = 1; i &lt;= m; i ++) {
		c[i] += c[i - 1];
	}
	for (i = n; i &gt;= 1; i --) {
		sa[c[x[y[i]]]] = y[i];
		c[x[y[i]]] --;
	}
	
	for (i = 1; i &lt;= n; i ++) {
		y[i] = x[i];
	}
	for (m = 0, i = 1; i &lt;= n; i ++) {
		if (y[sa[i]] == y[sa[i - 1]] &amp;&amp; y[sa[i] + k] == y[sa[i - 1] + k]) {
			x[sa[i]] = m;
		}
		else {
			m ++;
			x[sa[i]] = m;
		}
	}
	
	if (m == n) {
		break;
	}
}

}
int height[N], rk[N];
int mp[N];
LL ans[N];
void get_height() {
int i, j, k;
memset(height, 0, sizeof(height));
for (i = 1; i &lt;= n; i ++) {
	rk[sa[i]] = i;
}
for (k = 0, i = 1; i &lt;= n; i ++) {
	if (rk[i] == 1) {
		continue;
	}
	
	if (k) {
		k --;
	}
	
	int j = sa[rk[i] - 1];
	while (i + k &lt;= n &amp;&amp; j + k &lt;= n &amp;&amp; s[i + k] == s[j + k]) {
		k ++;
	}
	height[rk[i]] = k;
}

}
int main () {
ios::sync_with_stdio(False);
cin.tie(0);
int T;
cin &gt;&gt; T;
n = 0; 
for (int i = 1; i &lt;= T; i ++) {
	cin &gt;&gt; ss + 1;
	for (int j = 1; ss[j]; j ++) {
		n ++;
		s[n] = ss[j] - 'a';    // 这里一定要 - 'a'！！！不然会爆 long long 
		mp[n] = i;
	}
	ed[i] = n;
	n ++;
	m = s[n] = 26 + i;   // 间隔符：别管是啥妖魔鬼怪不一样就行，同时更新上限 m 
	// 只要字典序不插在中间干扰答案就行 
}

get_sa();
get_height();

LL mn = 0;
// mn：从上一个不同字符串的字典序相邻后缀到当前后缀的 LCP 最小值 
memset(ans, 0, sizeof(ans));
for (int i = 1; i &lt;= n; i ++) {
	LL L = height[i];
	mn = min(L, mn); 
	int mx = mp[sa[i]], my = mp[sa[i - 1]];
	if (mx == my) {   // 相邻俩后缀属于一个字符串 
		ans[mx] += ed[mx] - sa[i] + 1 - L;
		// 字符串 mx 加上自己以 sa[i] 为开头的剩下的不重复子串
		// 比如说从 sa[i] 到字符串结尾还剩 abc，height 为 2
		// 那么从 a 开始有 3（字符串剩下长度）个后缀：a，ab，abc
		// 再减掉 2（a 和 ab），就是不重复子串 
	}
	else {
		ans[mx] += ed[mx] - sa[i] + 1 - L;
		// 和前面那个一样，都是 mx 自身的答案贡献 
		ans[my] += mn - L;
		/* *** 难点
		 假设上一个不同字符串到当前的子串分别是：
		 ba，bb，bbb，bbbb，bbbc
		 除了中间三个全是 b 的所属同一个字符串 s，其他头尾两个都是不同的 
		 mn = 1，字符串 s 的答案贡献在 i = bb 时减了 b 
		 在 i = bbb 减了 b 和 bb 
		 在 i = bbbb 时减了 b 和 bb 和 bbb
		 在 i = bbbc 时减了 b 和 bb 和 bbb
		 我们发现同一个 b 的贡献在和别的字符串匹配时减了 2 次
		 但实际上 bbbb 字符串减 b 的贡献只用减 1 次
		 （本来要减 4 次，但剩下的 b 在 mx = my 时把自身重复的都减掉了） 
		 （我们这里只讨论 bbbb 在减掉自身相重复的子串后，与外界相重复的子串应该怎么减）
		 而 b 这个子串与其它两个字符串的后缀相重复，在 bbbb 内的贡献减 1 次就好
		 所以还要将 mn 加回来 
		 */
		mn = L;   // 更新 mn 
	}
}

for (int i = 1; i &lt;= T; i ++) {
	cout &lt;&lt; ans[i] &lt;&lt; "\n";
}

return 0;

}

后缀自动机 SAM 做法题解</p>

SAM 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
char s[N], ss[N];
int np, tot;
int len[N], v[N], slen[N];
int ch[N][30], fa[N];
LL ans[N];
void extend(int c) {
int p = np;
tot ++;
np = tot;
len[np] = len[p] + 1;
for (; p &amp;&amp; !ch[p][c]; p = fa[p]) {
	ch[p][c] = np;
}

if (!p) {
	fa[np] = 1;
}
else {
	int r = ch[p][c];
	
	if (len[r] == len[p] + 1) {
		fa[np] = r;
	}
	else {
		tot ++;
		int nr = tot;
		len[nr] = len[p] + 1;
		
		fa[nr] = fa[r];
		fa[r] = nr;
		fa[np] = nr;
		
		for (; p &amp;&amp; ch[p][c] == r; p = fa[p]) {
			ch[p][c] = nr;
		} 
		memcpy(ch[nr], ch[r], sizeof(ch[r]));
	}
}

}
void get_v(int x, int i) {
for (; x && v[x] != i && v[x] != -1; x = fa[x]) {

// 遇到 v[x] 不是当前字符串，那么 x 的后缀也不是当前字符串，直接退出就好
if (v[x] != 0) {
v[x] = -1;
}
else {
v[x] = i;
}
}
}
int main () {
ios::sync_with_stdio(False);
cin.tie(0);
tot = np = 1;
fa[1] = 0;
memset(len, 0, sizeof(len));
memset(v, 0, sizeof(v));
memset(ch, 0, sizeof(ch));

int n, sl = 0;
cin &gt;&gt; n;
for (int i = 1; i &lt;= n; i ++) {
	np = 1;
	cin &gt;&gt; ss + 1;
	slen[i] = strlen(ss + 1);
	for (int j = 1; ss[j]; j ++) {   // 神人出题人，搞得读入像坨 
		s[sl + j] = ss[j];
		extend(ss[j] - 'a');
	}
	sl += slen[i];
}

int x = 1, last = 0;
for (int i = 1; i &lt;= n; i ++) {
	x = 1;
	for (int j = 1; j &lt;= slen[i]; j ++) {
		x = ch[x][s[last + j] - 'a'];
		get_v(x, i);
	}
	last += slen[i];
}

memset(ans, 0, sizeof(ans));

for (int i = 1; i &lt;= tot; i ++) if (v[i] != -1) {
	ans[v[i]] += (len[i] - len[fa[i]]);
}

for (int i = 1; i &lt;= n; i ++) {
	cout &lt;&lt; ans[i] &lt;&lt; "\n";
}

return 0;

}

</p>

ID

6830

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

Hydro

3 条题解

思路

代码：

信息

状态

开发

支持

关于

3 条题解

思路

代码：

[USACO17DEC] Standing Out from the Herd P

信息

状态

开发

支持

关于

还没有账户？

登录