题解 | #String Problem# #ICPC# #沈阳# 题解

牛客24346M - String Problem

• https://ac.nowcoder.com/acm/contest/24346/M
• 来源：ICPC2021 · 沈阳

题意

• 给出一个长度为 $nn$ 的字符串，对于每个前缀，求最长的、字典序最大的子串，对于每个 $i\in [1,n]i\backslash in\; [1,n]$ 输出所求的子串的开始和结束位置。
• 样例：

  pbpbppb
  

  1 1
  1 2
  1 3
  1 4
  1 5
  5 6
  5 7 
  

• 对于每个 $i\in [1,n]i\backslash in\; [1,n]$，结束位置一定是 $ii$。
• 考虑用 SAM 处理结束位置的左端点的位置。
• 先思考几个前置知识：
  • 1. 对于每个 $i\in [1,n]i\backslash in\; [1,n]$，至少有一个 SAM 的 trie 节点与之对应。
  • 2. 对 SAM 的 trie 进行 DFS 遍历，每个作为子串右端点的 $i\in [1,n]i\backslash in\; [1,n]$ 都能遍历到。
• 所以，在 tire 树上进行 DFS 遍历，对于某个 tire 树节点，下一步优先遍历字典序靠后的字母。能够保证原串中的每个位置都被遍历到。

void DFS(int cur,int len)
{
	for (int i=25; i>=0; i--)
	{
		int nxt = sam.trie[cur][i];
		if(nxt && !vis[nxt])
		{
			vis[nxt] = true;
			DFS(nxt, len+1);
		}
	}
	if(!ans[sam.posi[cur]])//POSi是 trie树上的i节点 对应的子串的右端点 在原串中的位置
		ans[sam.posi[cur]] = sam.posi[cur]-len+1;
}

void Sol()
{
	sam.Init();
	sam.Build();
	DFS(1, 0);
	for (int i=1; i<=n; i++)
	{
		printf("%d %d\n",ans[i],i);
	}
}