首页 > 其他分享 >字典序相关字符串问题的 SAM 解法

字典序相关字符串问题的 SAM 解法

时间:2023-07-24 13:12:46浏览次数:41  
标签:SAM int len 后缀 link 解法 字典

前文(SAM 基础)

如果你并不是很熟 SAM,可以看看我远古时期的 blog:浅析后缀自动机 - -Wallace- - 博客园 (cnblogs.com)

缘起

为什么突然想到这个方面的东西,是因为在 ZJU 校队预组队时做到一个 CF-GYM-100418C,当时一眼 SA 但实际上根本不熟。赛后发现有位国外老哥随手 SAM 暴打,一点都不麻烦。

所以本来打算学学 SA,现在又改了主意。大多数观点认为字典序相关问题中 SA 常常占优势,现在我就来正经地来补一补 SAM 的这个短板。

并不是说 SA \(\subset\) SAM,这两者不能互相替代,比如 SAM 就有一个空间问题。不学 SA 只是我懒。

引入:后缀排序

首先对 \(s\) 的 反串 \(s^R\) 建立 SAM,得到的 parent tree 就是后缀树。

所谓后缀树,就是所有 \(s\) 的后缀插入到 Trie 中所得。这里通过将一段没有分支的长链压缩为单条边实现了 \(O(n)\) 复杂度。

考虑一个显而易见的事实:如果将每个点的出边按字典序排好,然后按序 dfs,得到的后缀就是有序的。现在主要的问题就是:如何求出每一条树上出边的 第一个字符

考虑还原到 \(s\) 串上。我们建立了反串 SAM,就维护出 \(s^R\) 上的 \(\text{endpos}\) 集合(也即 \(s\) 的 \(\text{startpos}\))中的 第一个元素

对于一个 \(f = link(x)\),从 \(f\) 到 \(x\) 的 \(\text{endpos}\) 发生改变,原因是在 \(maxlen(x)\) 后面一个出现不一样导致 \(\text{endpos}(f)\) 中的元素分家。这个第一个出现不一样的就在 \(s^R[\text{endpos}(x)_{any}-len(f)]\) 处。

那就好办,建 parent tree 的时候就记下这个字符,然后对每个点排序所有出边。

最后就是怎么判断是不是包含后缀的结点。如果包含后缀,当且仅当在 \(s^R\) 上 \(\min\limits_{i \in \text{endpos}(x)} i = len(x)\)。该等价类中最长的已经到头,而到头就意味着 \(s^R\) 的前缀也就是 \(s\) 的后缀。

不要忘了将 \(s^R\) 还原为 \(s\) 上的下标。

参考代码(由于空间缘故只能过 LOJ 模板):

#include <bits/stdc++.h>

#define link other_link
const int N = 1e6 + 5;
const int S = 62;

int ch[N * 2][S], link[N * 2], len[N * 2], right[N * 2];
int total = 1, last = 1;

void extend(int c, int pos) {
  int p = last, np = last = ++total;
  len[np] = len[p] + 1, right[np] = pos;
  for (; p && !ch[p][c]; p = link[p]) ch[p][c] = np;
  if (!p) { link[np] = 1; return; }
  int q = ch[p][c];
  if (len[q] == len[p] + 1) { link[np] = q; return; }
  int nq = ++total;
  memcpy(ch[nq], ch[q], S << 2);
  link[nq] = link[q], right[nq] = right[q];
  len[nq] = len[p] + 1, link[np] = link[q] = nq;
  for (; p && ch[p][c] == q; p = link[p]) ch[p][c] = nq;
}

char s[N];
int n;

std::vector<std::pair<char, int>> adj[N * 2];
std::vector<int> ans;
void dfs(int x) {
  if (x != 1 && right[x] == len[x])
    ans.push_back(n - right[x] + 1);
  for (auto [c, y] : adj[x])
    dfs(y);
}

int ord(char x) {
  if (isdigit(x)) return x - '0';
  else if (isupper(x)) return x - 'A' + 10;
  else return x - 'a' + 36;
}

signed main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);

  std::reverse(s + 1, s + 1 + n);
  for (int i = 1; i <= n; i++)
    extend(ord(s[i]), i);
  
  for (int i = 2; i <= total; i++) {
    int x = i;
    int f = link[x];
    char c = s[right[x] - len[f]];
    adj[f].emplace_back(c, x);
  }
  for (int i = 1; i <= total; i++)
    std::sort(adj[i].begin(), adj[i].end());
  dfs(1);

  for (auto x : ans)
    printf("%d ", x);
  puts("");

  return 0;
}

关于反串 \(s^R\)

为什么要反转?

考虑正串 \(s\) 上的字典序是从左到右,而直接对 \(s\) 建 SAM 得到的是“后缀链接 \(link\)”。

我们要的是“前缀链接”,每次上跳一个前缀,即在前缀相同的情况下向下跳实现向后的追加——这和字典序比较的过程时近乎相同的。

于是反转 \(s\),对 \(s^R\) 建 SAM,得到的就是前缀链接而非后缀链接,得到的是 \(startpos\) 而非 \(endpos\)。

例题

【CFGYM-100418C】Substrings

题意

给定一个串 \(s\),\(q\) 次询问,每次问 \(s\) 的所有子串中字典序小于 \(s[l,r]\) 的个数。

题解

如上文,按字典序建的 \(s^R\) 的 parent tree 完成后,等价类中的所有串的排名(\(s\) 所有子串的字典序排名)一定连续。

联系到 Trie 的知识可知,按字典序 dfs 得到的 dfs 序(dfn)就是这些等价类的排名。实际上也就能理解为是所有子串的排名。

对于一个 \(s[l, r]\),我们用家喻户晓的倍增法定位到其所属的等价类中,然后所有满足 dfn 在该等价类(即该结点)之前的结点都是字典序在其之前的点都是字典序小于 \(s[l, r]\) 的。

一个在 dfn 上的前缀和就能搞定。对于自己这个等价类也是只要看看有多少比自己小的串即可。

时间瓶颈在倍增,复杂度 \(O(|s|+q\log |s|)\)。

【LOJ2102】「TJOI2015」弦论

题意

求 \(s\) 所有子串中字典序升序 \(k-\text{th}\) 的子串。分是否考虑本质不同两种。

题解

有一个 DAG 上走的算法这里不赘述。

考虑按字典序建的 \(s^R\) 的 parent tree 上 dfs,每次走到一个点就将 \(k\) 减去该点所代表的串的数量(分两种情况),直到不够减(此时剩下的为 \(k'\)),说明这个结点(\(x\))就含有所求的答案:

如果要求本质不同,长度为 \(len(link(x)) + k'\) 的串就是所求。

如果重复计算本质不同,长度为 \(len(link(x)) + \left\lceil\dfrac{k}{|\text{endpos(x)}|}\right\rceil\) 的即为所求。

结语

如上,一些基本的字典序 & 子串的题目 SAM 是可以胜任的,或者说其实是背后的那个后缀树在起主要作用。

DAG 的作用在逐渐被替代,但也没有完全替代我也不好说。

标签:SAM,int,len,后缀,link,解法,字典
From: https://www.cnblogs.com/Lice-wx/p/lexico-sam.html

相关文章

  • Python【12】 字典的get()方法
    返回指定键的值。参考:https://www.runoob.com/python/att-dictionary-get.html......
  • Python【13】 字典的 items( ) 方法
    类似于字典转元组的效果,但又不完全是参考:https://www.runoob.com/python3/python3-att-dictionary-items.html......
  • 显示python字典key
    如何显示Python字典的key作为一名经验丰富的开发者,我将向你解释如何在Python中显示字典的键。以下是整个过程的步骤概述:步骤描述步骤1创建一个包含键值对的字典步骤2使用keys()方法获取字典的键步骤3遍历键并显示现在让我们一步步地来实现。步骤1:创建一......
  • java: 找不到符号 符号: 类 SampleAqlQuantizer 位置: 程序包 com.si.model.entit
    解决"java:找不到符号符号:类SampleAqlQuantizer位置:程序包com.si.model.entit"的问题作为一名经验丰富的开发者,我将指导你解决这个问题。首先,我们需要了解整个解决问题的流程。下面是一个表格展示了步骤和对应的操作:步骤操作1.检查类的包名和导入的包是否正确......
  • python 字典求差集
    Python字典求差集在Python中,字典(Dictionary)是一种无序的、可变的数据类型,它由一系列键(Key)和对应的值(Value)组成。字典的特点是可以通过键来访问对应的值,并且键必须是唯一的。在某些场景中,我们可能需要对字典进行一些操作,如求差集。本文将介绍Python字典求差集的方法,并给出相应的代......
  • python 字典 子集
    Python字典子集介绍在Python编程语言中,字典(dictionary)是一种无序、可变和可迭代的数据类型。字典由键(key)和对应的值(value)组成,每个键值对(key-valuepair)之间用逗号隔开,整个字典被花括号包围。字典是一种非常常用的数据结构,用于存储和管理大量的数据。在本文中,我们将探讨Python字......
  • python如何提取字典中的value
    项目方案:提取字典中的value1.项目背景在Python编程中,字典(Dictionary)是一种非常常用的数据结构,它可以存储键值对,而且键是唯一的。在实际开发中,经常需要从字典中提取value进行处理和分析。本项目的目标是探索如何高效地提取字典中的value。2.代码示例以下是一些常用的方法,可用......
  • 字典dict转字符串
    在Python中,可以使用不同的方法将字典转换为字符串。以下是几种常用的方法:使用str()函数:emy_dict={'key1':'value1','key2':'value2','key3':'value3'}dict_str=str(my_dict)print(dict_str)#输出:{'key1':'value......
  • sam自动生成mask代码解析
    要自动生成mask,请向“SamAutomaticMaskGenerator”类注入SAM模型(需要先初始化SAM模型)importsyssys.path.append("..")fromsegment_anythingimportsam_model_registry,SamAutomaticMaskGenerator,SamPredictorsam_checkpoint="sam_vit_b_01ec64.pth"model_type......
  • python3字典添加键值对
    如何在Python3中添加字典键值对概述在Python中,字典(Dictionary)是一种非常有用的数据结构,它可以存储键值对。如果你刚入行并且不知道如何在Python3中添加字典键值对,不用担心!本文将指导你完成这个任务。步骤概览下面是完成这个任务的步骤概览:步骤描述1创建一个空字典......