AcWing 1053. 修复DNA
原题链接
困难
作者:
皓首不倦
,
2021-06-23 05:24:19
,
所有人可见
,
阅读 521
# import sys
# sys.stdin = open("data.txt", "r")
'''
基于AC自动机的DP
'''
from collections import deque
from functools import lru_cache
class AcTrieNode:
def __init__(self, fa):
self.s = ''
self.fail_s = []
self.next = {}
self.is_end = False
self.fail = None
self.fa = fa
self.id = 0
class AcTrie:
def __init__(self):
self.root = AcTrieNode(None)
self.__idx = 1
def append(self, s: str):
cur = self.root
for ch in s:
if ch not in cur.next:
new_node = AcTrieNode(cur)
new_node.id = self.__idx
self.__idx += 1
new_node.s = cur.s + ch
cur.next[ch] = new_node
cur = cur.next[ch]
cur.is_end = True
def build(self, s_list = []):
for s in s_list:
self.append(s)
que = deque()
que.append(self.root)
depth = 0
while len(que) > 0:
node_num = len(que)
for _ in range(node_num):
cur = que.popleft()
if depth == 1:
cur.fail = self.root
elif depth != 0:
cur.fail = self.root
p = cur.fa.fail
last_ch = cur.s[-1]
while True:
if not p:
break
if last_ch in p.next:
cur.fail = p.next[last_ch]
f = cur.fail
if f.is_end:
cur.fail_s.append(f.s)
for s in f.fail_s:
cur.fail_s.append(s)
break
else:
p = p.fail
for new_node in cur.next.values():
que.append(new_node)
depth += 1
# 获取节点状态转移的表 [0号点转移表,1号点转移表, ......]
def get_stat_map(self):
ans = [{'A':None, 'G':None, 'C':None, 'T':None} for _ in range(self.__idx)]
def dfs(node: AcTrieNode):
for ch in 'AGCT':
if ch in node.next:
if node.next[ch].is_end or len(node.next[ch].fail_s) != 0:
# 发生了匹配,下一个字符不可能是ch
ans[node.id][ch] = None
else:
ans[node.id][ch] = node.next[ch].id
else:
cur = node
while True:
if ch in cur.next:
if cur.next[ch].is_end or len(cur.next[ch].fail_s) != 0:
# 发生了匹配,下一个字符不可能是ch
ans[node.id][ch] = None
else:
ans[node.id][ch] = cur.next[ch].id
break
else:
if cur.fail is not None:
cur = cur.fail
else:
ans[node.id][ch] = cur.id
break
for child in node.next.values():
dfs(child)
dfs(self.root)
return ans
case_id = 1
while True:
n = int(input())
if n == 0:
break
ac_trie = AcTrie()
for _ in range(n):
ac_trie.append(input())
ac_trie.build()
stat_map = ac_trie.get_stat_map()
s = input().strip()
cache = [[None]*(len(s)+1) for _ in range(20*n)]
n = len(s)
# dp(stat, ii)表示Ac自动机状态为stat情况下,继续构造出一个合法的字符串[ii:n]这一段的最少需要修改的次数
def dp(stat, ii):
if ii == n:
return 0
if cache[stat][ii] is not None:
return cache[stat][ii]
ans = 0x7fffffff
for ch in 'AGCT':
if stat_map[stat][ch] is None:
continue
t = 0
if s[ii] != ch:
t += 1
t += dp(stat_map[stat][ch], ii+1)
ans = min(ans, t)
# print(stat, ii, ans, n)
cache[stat][ii] = ans
return ans
ans = dp(ac_trie.root.id, 0)
print(f'Case {case_id}: {ans if ans != 0x7fffffff else -1}')
case_id += 1