把无限链看成禁止串 AC 自动机上的双无限路径,缩点成 DAG 后按「环 SCC 起、有限路径、环 SCC 收」数路径,遇多环或非简单环环节则判无穷。
OJ: roj
题目 ID: 1708
难度:提高+/省选-
标签:字符串AC自动机强连通分量拓扑排序python
创建: 2026-10-07 17:47
更新: 2026-10-07 17:47
形式化题目
字母表取前
- 合法性:任意位置
起的子串 都不等于 ( ); - 去重规则:两条链
视为同一条当且仅当存在整数 使 对一切 成立, 即二者互为平移。
输出满足条件的不同链数;若有无穷多条输出
题面给的第一个例子是 b、后半段全是 a,交界处唯一的 ba 不含禁止串 ab)。
正解
思路
把链变成自动机上的路径。 先用
链是双无限的,所以对应的是一条双无限走法(两侧都无限长)。去掉禁止结点与射向它们的转移后,
得到一张有向图
为什么要缩点。 图
两端的 SCC 必须能提供"无限次走",也就是必须含环;中间的 SCC 只能提供有限的一段。
什么时候答案是
- 某个含环的 SCC 不是简单环。 在
个顶点的 SCC 里,内部边数至少 ; 恰好等于 时它是一条简单环,从任一顶点出发的无限走法唯一; 一旦内部边数 顶点数,同一段无限走法就有了至少两种走法(可以选不同的环、或绕不同圈数), 链的数量无穷。所以只要存在 inner > size的 SCC,直接输出。 - DAG 路径上有
个环 SCC。 三个环中夹在中间的那个可以任意绕圈: 绕 圈与绕 圈得到的两条链不可能互为平移(平移保长度结构),所以链无穷。 因此路径上环 SCC 数达到 就输出 。
排除这两种情况后,中间夹着的 SCC 全部是无自环的单点,走法是唯一的;
两端的环 SCC 都是简单环,无限走法也是唯一的。所以一条「环 SCC
路径计数。 在缩点 DAG 上做拓扑 DP:pathCnt[v] 表示"从某个环 SCC 出发、终点恰为 cycleOnPath[v] 表示这些路径上环 SCC 个数的最大值(用于上面的 pathCnt 之和
(按"收尾的环 SCC"给链归类)。
用两个小例子核对。 第一个例子 a),
ab 的结尾是禁止结点。去掉禁止结点后剩下的转移是
| 收尾 SCC | 路径 | 对应链 |
|---|---|---|
| 长度 |
||
| 长度 |
||
三条,与题面一致。
第二个例子
实现要点。 AC 自动机要用 BFS 把转移补齐成完整转移表(失配时该走到哪个状态),
并在 BFS 中把禁止标记沿 fail 链传递;Tarjan 求 SCC 时顺带统计每个 SCC 的顶点数与内部边数——
内部边数的统计必须在原图上做(comp[u] == comp[v] 的边),跨 SCC 的边才建成 DAG。Python 版
Tarjan 写成显式栈的迭代版,避免链状自动机把递归压爆。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 17:47
# update_at: 2026-10-07 17:47
import sys
from collections import deque
type Graph = list[list[int]] # 邻接表:graph[u] 是结点 u 的出边终点列表
def build_machine(t: int, pats: list[str]) -> tuple[list[list[int]], list[bool]]:
"""建禁止串的 AC 自动机,返回补齐后的转移表和「禁止」标记(已沿 fail 链传递)。"""
nxt = [[0] * t]
banned = [False]
for pat in pats:
u = 0
for ch in pat:
c = ord(ch) - 97
if nxt[u][c] == 0:
nxt[u][c] = len(nxt)
nxt.append([0] * t)
banned.append(False)
u = nxt[u][c]
banned[u] = True
fail = [0] * len(nxt)
que = deque(c for c in nxt[0] if c) # 根的直接儿子(0 表示根本没有这个儿子)
while que:
u = que.popleft()
banned[u] = banned[u] or banned[fail[u]] # 禁止标记沿 fail 链下传
row = nxt[u]
for c in range(t):
if row[c]:
fail[row[c]] = nxt[fail[u]][c]
que.append(row[c])
else:
row[c] = nxt[fail[u]][c] # 补齐转移:失配后该走到哪
return nxt, banned
def strong_components(graph: Graph) -> list[int]:
"""Tarjan 求强连通分量(迭代版,避免深递归),返回每个结点所属的 SCC 编号。"""
m = len(graph)
dfn = [-1] * m # -1 表示还没访问过
low = [0] * m
comp = [-1] * m
on_stack = [False] * m
stack: list[int] = [] # Tarjan 栈
clock = 0
comp_cnt = 0
for root in range(m):
if dfn[root] >= 0:
continue
work = [(root, 0)] # (结点, 下一条要看的出边下标)
while work:
u, i = work[-1]
if i == 0:
dfn[u] = low[u] = clock
clock += 1
stack.append(u)
on_stack[u] = True
if i < len(graph[u]):
work[-1] = (u, i + 1)
v = graph[u][i]
if dfn[v] < 0:
work.append((v, 0))
elif on_stack[v]:
low[u] = min(low[u], dfn[v])
else:
work.pop()
if low[u] == dfn[u]: # u 是这个 SCC 里第一个被访问的结点
while True:
w = stack.pop()
on_stack[w] = False
comp[w] = comp_cnt
if w == u:
break
comp_cnt += 1
if work:
p = work[-1][0]
low[p] = min(low[p], low[u])
return comp
def count_chains(t: int, pats: list[str]) -> int:
"""统计两端都无限、平移视为同一条的合法链数量;有无穷多条时返回 -1。"""
nxt, banned = build_machine(t, pats)
# 只有「非禁止结点 + 非禁止转移」上的双无限路径才是合法链
graph: Graph = [
[v for v in nxt[u] if not banned[v]] if not banned[u] else [] for u in range(len(nxt))
]
comp = strong_components(graph)
size = [0] * (max(comp) + 1) # 每个 SCC 的结点数
inner = [0] * (max(comp) + 1) # 每个 SCC 的内部边数
for u in range(len(nxt)):
if banned[u]:
continue
size[comp[u]] += 1
inner[comp[u]] += sum(1 for v in graph[u] if comp[v] == comp[u])
# SCC 是简单环 ⟺ 内部边数等于结点数;多出来的边意味着这个 SCC 自己就能造出无穷多条链
if any(inner[c] > size[c] for c in range(len(size))):
return -1
is_cycle = [size[c] > 0 and inner[c] == size[c] for c in range(len(size))]
out: Graph = [[] for _ in size]
indeg = [0] * len(size)
for u in range(len(nxt)):
if banned[u]:
continue
for v in graph[u]:
if comp[u] != comp[v]:
out[comp[u]].append(comp[v]) # 缩点 DAG 保留重边:不同转移是不同的链
indeg[comp[v]] += 1
# 链 = 「环 SCC 起 + DAG 有限路径 + 环 SCC 收」,按拓扑序数路径
path_cnt = [0] * len(size) # 从某个环 SCC 出发、终点是这个 SCC 的路径条数
cycle_on_path = [0] * len(size) # 这些路径上环 SCC 个数的最大值
que = deque(c for c in range(len(size)) if indeg[c] == 0)
for c in que:
cycle_on_path[c] = 1 if is_cycle[c] else 0 # 路径可以就从自己这个环开始
while que:
u = que.popleft()
if cycle_on_path[u] >= 3: # 夹在中间的环 SCC 能绕任意圈:无穷多条
return -1
if is_cycle[u]:
path_cnt[u] += 1 # 长度 0 的路径:自己就是一个环
for v in out[u]:
path_cnt[v] += path_cnt[u]
cycle_on_path[v] = max(cycle_on_path[v], cycle_on_path[u] + (1 if is_cycle[v] else 0))
indeg[v] -= 1
if indeg[v] == 0:
que.append(v)
return sum(path_cnt[c] for c in range(len(size)) if is_cycle[c])
def solve() -> None:
tokens = iter(sys.stdin.buffer.read().split())
t = int(next(tokens))
n = int(next(tokens))
pats = [next(tokens).decode() for _ in range(n)]
print(count_chains(t, pats))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 17:47
* update_at: 2026-10-07 17:47
*/
// 1708 无限链计数
// 一条双无限链(左右都能平移,平移后视为同一条)就是禁止串 AC 自动机上的
// 一条双无限转移路径;把非终止结点、非终止转移缩成 SCC 之后,路径的 SCC
// 序列在缩点 DAG 上单调,所以每条链恰好对应「环 SCC 出发 + DAG 有限路径 +
// 环 SCC 收尾」这样一条 DAG 路径:
// * SCC 内部边数 > 结点数 ⟺ 这个 SCC 不是简单环 ⟺ 链有无穷多条(-1);
// * DAG 路径上夹在中间的环 SCC 还能随便绕圈,所以路径上环 SCC 数 ≥ 3 时
// 也有无穷多条(-1);
// * 否则答案就是「环 SCC 到环 SCC」的 DAG 路径条数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXNODE = 10005; // 禁止串总长 ≤ 1000 × 10 = 10000,结点数 ≤ 10001
const int MAXE = 60005; // 每个非终止结点至多 t ≤ 6 条非终止转移
int t, n; // t:字母表大小;n:禁止串个数
int trie[MAXNODE][6]; // AC 自动机的完整转移(fail 指针补齐之后)
int failLink[MAXNODE]; // 失配指针
bool terminal[MAXNODE]; // 该结点或它的某个 fail 祖先是禁止串的结尾
int nodeCnt; // 结点个数,根固定为 0
// 一张图的链式前向星:g1 是「非终止结点 + 非终止转移」的原图,
// g2 是缩点后的 DAG(保留重边,重边代表不同的转移,必须分别计数)
struct Edge {
int to;
int next;
};
Edge g1[MAXE];
Edge g2[MAXE];
int head1[MAXNODE], head2[MAXNODE];
int cnt1, cnt2;
void add_edge1(int u, int v) {
cnt1++;
g1[cnt1].to = v;
g1[cnt1].next = head1[u];
head1[u] = cnt1;
}
void add_edge2(int u, int v) {
cnt2++;
g2[cnt2].to = v;
g2[cnt2].next = head2[u];
head2[u] = cnt2;
}
// 把一个禁止串插入 Trie
void insert_word(const char *s) {
int u = 0;
for (int i = 0; s[i]; i++) {
int c = s[i] - 'a';
if (trie[u][c] == 0) trie[u][c] = ++nodeCnt;
u = trie[u][c];
}
terminal[u] = true;
}
// 建 fail 指针,同时把转移补齐成「走到哪个状态」的完整转移表,
// 并把禁止标记沿 fail 链传递到每个结点
void build_fail() {
queue<int> que;
for (int c = 0; c < t; c++)
if (trie[0][c]) que.push(trie[0][c]);
while (!que.empty()) {
int u = que.front();
que.pop();
terminal[u] = terminal[u] || terminal[failLink[u]]; // fail 链传递
for (int c = 0; c < t; c++) {
if (trie[u][c]) {
failLink[trie[u][c]] = trie[failLink[u]][c];
que.push(trie[u][c]);
} else {
trie[u][c] = trie[failLink[u]][c];
}
}
}
}
int dfn[MAXNODE], low[MAXNODE], timerClock;
int stk[MAXNODE], top;
bool inStack[MAXNODE];
int sccId[MAXNODE], sccCnt;
int sccNode[MAXNODE]; // 每个 SCC 的结点数
int sccInner[MAXNODE]; // 每个 SCC 的内部边数
bool isCycleScc[MAXNODE]; // 内部边数 == 结点数 ⟺ 这个 SCC 就是一个简单环
// Tarjan 求强连通分量(只跑原图上非终止的结点)
void tarjan(int u) {
dfn[u] = low[u] = ++timerClock;
stk[++top] = u;
inStack[u] = true;
for (int e = head1[u]; e; e = g1[e].next) {
int v = g1[e].to;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (inStack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
sccCnt++;
int k;
do {
k = stk[top--];
inStack[k] = false;
sccId[k] = sccCnt;
sccNode[sccCnt]++;
} while (k != u);
}
}
int indeg[MAXNODE]; // 缩点 DAG 上每个 SCC 的入度,用来做 Kahn 拓扑排序
ll pathCnt[MAXNODE]; // pathCnt[v]:从某个环 SCC 出发、终点是 v 的 DAG 路径条数
int cycleOnPath[MAXNODE]; // cycleOnPath[v]:这些路径上环 SCC 个数的最大值
int main() {
scanf("%d %d", &t, &n);
char s[15];
for (int i = 0; i < n; i++) {
scanf("%s", s);
insert_word(s);
}
build_fail();
// 建原图:结点和转移都不能碰到禁止串
for (int u = 0; u <= nodeCnt; u++) {
if (terminal[u]) continue;
for (int c = 0; c < t; c++) {
int v = trie[u][c];
if (terminal[v]) continue;
add_edge1(u, v);
}
}
for (int u = 0; u <= nodeCnt; u++)
if (!terminal[u] && !dfn[u]) tarjan(u);
// 缩点:统计 SCC 内部边数,跨 SCC 的边建成 DAG
for (int u = 0; u <= nodeCnt; u++) {
if (terminal[u]) continue;
for (int e = head1[u]; e; e = g1[e].next) {
int v = g1[e].to;
if (sccId[u] == sccId[v]) {
sccInner[sccId[u]]++;
} else {
add_edge2(sccId[u], sccId[v]);
indeg[sccId[v]]++;
}
}
}
for (int i = 1; i <= sccCnt; i++) {
if (sccInner[i] > sccNode[i]) { // 不是简单环:同一个 SCC 里就有无穷多条链
printf("-1\n");
return 0;
}
if (sccInner[i] == sccNode[i]) isCycleScc[i] = true;
}
// 缩点 DAG 上按拓扑序做路径计数
queue<int> que;
for (int i = 1; i <= sccCnt; i++) {
if (indeg[i] == 0) {
que.push(i);
cycleOnPath[i] = isCycleScc[i] ? 1 : 0; // 路径可以就从自己这个环开始
}
}
while (!que.empty()) {
int u = que.front();
que.pop();
if (cycleOnPath[u] >= 3) { // 中间的环 SCC 可以绕任意圈:无穷多
printf("-1\n");
return 0;
}
if (isCycleScc[u]) pathCnt[u]++; // 长度 0 的路径:自己就是一个环
for (int e = head2[u]; e; e = g2[e].next) {
int v = g2[e].to;
pathCnt[v] += pathCnt[u];
cycleOnPath[v] = max(cycleOnPath[v], cycleOnPath[u] + (isCycleScc[v] ? 1 : 0));
if (--indeg[v] == 0) que.push(v);
}
}
ll answer = 0;
for (int i = 1; i <= sccCnt; i++)
if (isCycleScc[i]) answer += pathCnt[i]; // 每条链以收尾的环 SCC 归类,不重不漏
printf("%lld\n", answer);
return 0;
}复杂度
- 时间:建 AC 自动机
;建图 ;Tarjan 与缩点 ; 缩点 DAG 上拓扑 DP 。顶点数 , 边数 。故总时间 ,与 线性。 实测 10 个数据点中最大者( 、 、串长 )CPython 约 s, C++ 版本在 下更快,远低于 3000 ms 限时。 - 空间:AC 自动机转移表
,图与 Tarjan 辅助数组 , 合计约 ;C++ 用全局静态数组( MAXNODE = 10005、MAXE = 60005), 峰值内存远低于 256 MB。Python 的邻接表形式在顶格数据下也只有几 MB。 - 与
main.cpp的关系:两者是同算法同复杂度,main.cpp用链式前向星 + 显式队列 + 递归 Tarjan,main.py用邻接表 + 迭代 Tarjan,输出完全一致(10/10 逐字节相同)。 本题不存在 Python 特有的 TLE 风险。
总结
- 先去禁止串,再谈计数:AC 自动机把"不含禁止串"变成"路径不碰禁止结点", 多串匹配问题随之转成一张图上的路径问题。
- 双无限 + 缩点 = 有限长度的 DAG 路径:拓扑序不能后退,所以两侧无限的走法只能 用有限多个 SCC,链的结构被压缩成"环 SCC + DAG 有限路径 + 环 SCC"三段。
- 无穷多有两个来源,且彼此独立:SCC 内部边数超过顶点数(不是简单环),
或 DAG 路径上环 SCC 个数
(中间的环可以随便绕)。二者都直接输出 。 - 缩点必须保留重边:平行的两条转移是不同的链,删重边会漏计数。
- 路径计数按收尾 SCC 归类:以"终点所在的环 SCC"给链分类,
sum(pathCnt[环 SCC])不重不漏。 - 注:本题素材源目录里带有
data.py,随仓data/是按题面范围(、 、 串长 )自行构造的分层数据;题面本身是网络重建的版本, 文字表述以仓库内 content.md(即problem.md)为准。