python实现序列自动机(朴素、二分)

您所在的位置：网站首页 › python序列的类型 › python实现序列自动机(朴素、二分)

python实现序列自动机(朴素、二分)

2023-03-23 12:57| 来源: 网络整理| 查看: 265

序列自动机

序列自动机是一个可以快速判断任意字符串 a a a 是否包含子串 b b b 的算法。假定我们有一个串 a a a，和数组 n x t nxt nxt 。其中， n x t i , j nxt_{i, j} nxti,j表示在串 a a a 中，从第 i i i 个位置后的字母表中第 j j j 个元素首次出现的位置。

朴素做法

字母表是符号的有穷非空集合。我们规定，使用 ∑ \sum ∑表示字母表。常见字母表有： 1. ∑ = { a , b , … , z } \sum=\{a, b, \dots, z \} ∑={a,b,…,z}:小写字母集合 2. ∑ = { 0 , 1 , … , 9 } \sum=\{0, 1, \dots, 9 \} ∑={0,1,…,9}:十进制字母表 3. ∑ = { 0 , 1 } \sum=\{0, 1\} ∑={0,1}:二进制字母表

构造

若 a a a 为以上几种常见字母表,即可初始化 n x t nxt nxt 为 l e n ( a ) × ∣ ∑ ∣ len(a)\times |\sum| len(a)×∣∑∣ 大小的初始化值为 I N F INF INF 的数组。 I N F INF INF表示第 i i i 个位置后的没有出现字母表中第 j j j 个元素。

我们从末尾往前依次计算当前出现的位置。对应每个 i i i , n x t i , j = n x t i + 1 , j nxt_{i, j} = nxt_{i + 1, j} nxti,j=nxti+1,j, 对应 a [ i ] a[i] a[i] 字符而言，其首次出现的位置当然是 i i i 。

以下示例中 a a a 为小写字母集合。

a = input() b = input() n = len(a) nxt = [[INF] * 26 for _ in range(n + 2)] for i in range(n - 1, -1, -1): for j in range(26): nxt[i][j] = nxt[i + 1][j] nxt[i][ord(a[i]) - ord('a')] = i 查找子串操作

初始化 l s t p o s lstpos lstpos 为 − 1 -1 −1 ，含义为字串 b [ i − 1 ] b[i-1] b[i−1] 对应 a [ ] a[] a[] 中的下标。

lstpos = -1 for i in range(len(b)): lstpos = nxt[lstpos + 1][ord(b[i]) - ord('a')] if lstpos == INF: return False else: return True 复杂度

时间复杂度: O ( l e n ( a ) × ∣ ∑ ∣ + l e n ( b ) ) O(len(a)\times |\sum| + len(b)) O(len(a)×∣∑∣+len(b)) 空间复杂度: O ( l e n ( a ) × ∣ ∑ ∣ ) O(len(a)\times |\sum|) O(len(a)×∣∑∣)

\quad

优化做法(二分)

P5826 【模板】子序列自动机当 ∣ ∑ ∣ |\sum| ∣∑∣很大时，空间复杂度过高。修改 n x t i nxt_i nxti 存储 i i i 字符所在的下标。从 a a a 串开头进行遍历，保证 n x t i nxt_i nxti 的单调性。

修改的二分模板中，若 n x t [ b [ i ] ] nxt[b[i]] nxt[b[i]] 中已经没有 ≥ l s t p o s + 1 \geq lstpos + 1 ≥lstpos+1 的下标，则返回 l e n ( n x t [ b [ i ] ] ) len(nxt[b[i]]) len(nxt[b[i]]) (类似朴素做法中的 I N F INF INF)。

import os, sys input = lambda: sys.stdin.readline().rstrip("\r\n") printf = lambda d: sys.stdout.write(str(d) + "\n") def read(): line = sys.stdin.readline().strip() while not line: line = sys.stdin.readline().strip() return map(int, line.split()) def I(): return int(input()) type, n, q, m = read() a = list(read()) nxt = [[] for _ in range(int(1e5) + 2)] # 存储a[]中每个字符对应的下标 for i in range(n): nxt[a[i]].append(i) def binary(t, x): # >= x的二分模板 l = 0 r = len(t) # 这里设置r = len(t) 而不是 len(t) - 1，便于下面判断 while l > 1 if t[mid] >= x: r = mid else: l = mid + 1 return l for _ in range(q): b = list(read()) lstpos = -1 # 字串b[i-1]对应a[]中的下标 length = b.pop(0) for i in range(length): if len(nxt[b[i]]) == 0: # 若a[]串中不含有b[i]字符则直接返回 printf('No') break tmp = binary(nxt[b[i]], lstpos + 1) # 否则二分查找 # nxt[b[i]]中>= lstpos + 1的下标 if tmp >= len(nxt[b[i]]): printf('No') break lstpos = nxt[b[i]][tmp] # 记录 b[i]在a[]的下标 else: printf('Yes') C. Obtain The String

题意 t t t 串中由多少个 s s s的子串拼接而成。这里给出朴素做法。

import os, sys input = lambda: sys.stdin.readline().rstrip("\r\n") printf = lambda d: sys.stdout.write(str(d) + "\n") INF = 9999999999999 def read(): line = sys.stdin.readline().strip() while not line: line = sys.stdin.readline().strip() return map(int, line.split()) def I(): return int(input()) for _ in range(I()): s = input() t = input() n = len(s) nxt = [[INF] * 26 for _ in range(n + 2)] for i in range(n - 1, -1, -1): for j in range(26): nxt[i][j] = nxt[i + 1][j] nxt[i][ord(s[i]) - ord('a')] = i res = 1 pos = -1 for i in range(len(t)): if pos == n: res += 1 pos = 0 if nxt[pos + 1][ord(t[i]) - ord('a')] == INF: pos = -1 res += 1 if nxt[pos + 1][ord(t[i]) - ord('a')] == INF and pos == -1: res = INF break pos = nxt[pos + 1][ord(t[i]) - ord('a')] if res >= INF: print(-1) else: print(res)

【本文地址】

python实现序列自动机(朴素、二分)

python实现序列自动机(朴素、二分)

今日新闻

推荐新闻