zcmimi's blog

arrow_back字符串共9篇文章

avatar
zcmimi
2020-09-02 07:35:00
avatar
zcmimi
2020-07-22 19:57:00

普通的单模式串匹配

给定模式串A(|A|=m)、文本串B(|B|=n),需要求出所有位置p,满足B串从第p个字符开始的连续m个字符,与A串完全相同

定义匹配函数C(x,y)=[A(x)-B(y)]^2,若A的第x个字符与B的第y个字符匹配

avatar
zcmimi
2020-05-13 19:00:00

简介

后缀数组,又称SA

是OI中处理字符串的有力工具

实现

有两种实现的方法

  1. 倍增法
  2. DC3

这里主要讲倍增法

sa[i]表示所有后缀中的字典序排名为i的后缀的起始位置

rnk[i]表示起始位置为i的后缀(后缀i)在所有后缀中的排名

avatar
zc
2020-10-13 21:01:06

查看原题

点击跳转

首先将所有RNA序列插入trie

然后用病毒模版片段trie上搜索

对于?,可以匹配任意一种

对于*,可以选择

  1. 不匹配,*当作没有
  2. 匹配,下一个停止用*匹配
  3. 匹配,下一个继续用*匹配
avatar
zc
2020-10-13 19:58:29

查看原题

点击跳转

f[i][j]表示用完前i个通配符,是否能匹配[1,j],

s为含通配符字符串,t为目标字符串,p_i为第i个通配符的位置

下文x|=y表示: 若y能,则x也能

若第i个通配符为*,*可以代替j之后的所有字符

那么f[i][j]|=f[i][j-1],也就是用*继续匹配下去(j-1位之后用*匹配)

s[p_i+1,p_{i+1}-1]=t[j+1,j+p_{i+1}-p_i-1],

那么f[i+1][j+(p_{i+1}-1)-(p_i+1)+1+[s[p_{i+1}]=?]]|=1

其中[s[p_{i+1}]='?']s[p_{i+1}]?时为1,否则为0

详见代码

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

设通配符的数值为0,定义匹配函数C(x,y)=[A(x)-B(y)]^2A(x)B(y),那么\displaystyle P(x)=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)

按照套路,翻转A串得到S串:

\displaystyle \begin{aligned} P(x) &=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)\\ &=\sum_{i=0}^{m-1}[S(m-i+1)-B(x-m+i+1)]^2S(m-i+1)B(x-m+i+1)\\ &=\sum_{i=0}^{m-1}S(m-i+1)^3B(x-m+i+1)+\\ &\quad\sum_{i=0}^{m-1}B(x-m+i+1)^3S(m-i+1)-\\ &\quad2\sum_{i=0}^{m-1}S(m-i+1)^2B(x-m+i+1)^2 \end{aligned}

写为卷积形式:

\displaystyle P(x)=\sum_{i+j=x}S(i)^3B(j)+S(i)B(j)^3-2S(i)^2B(j)^2

avatar
zc
2020-05-05 00:18:00
查看原题

点击跳转

枚举变换情况(6!),然后kmp\Theta(n)判断即可

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

n\le12

f[sta][x]表示状态为sta,当前位置为x的情况下最短的(字典序最小)

f[sta][y]=\min(f[sta'][x]+cost)

看到这个可以联想到AC自动机最短路(貌似是最短哈密顿路径?)

每个字符串长度都小于50,如果用AC自动机可能就核弹打蚊子

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

删除完这个字符串后面的就接到前面

我们可以想到用栈解决

然后判断剩下的串当前位置是否和目标字符串匹配我们可以用hash来解决

1/1
Search
search