夢に僕らで帆を張って
来るべき日のために夜を超え

标签 字符串 下的文章

October 31, 2019

洛谷P3966/TJOI2013 单词

题意给出$n$个单词,求每个单词共出现几次数据范围:单词总长度$\le 10^6$题解多模匹配,使用$\text{AC}$自动机解决需要注意的是,可能出现重复的单词;为避免字典树的值被覆盖,只记录第一个编号,而将其他相同的单词指向这个编号统计答案时,在该前缀的所有后缀上($\text{Fail}$树上的祖先节点上),将其自身答案累加上去,就是总共出现的次数代码:#include<ios...
October 27, 2019

洛谷P3193/HNOI2008 GT考试

题意求有多少个$n$位的字符串不包含$m$位的字符串数据范围:$n \le 10^9,m \le 20,k \le 1000$题解用$f[i][j]$表示长串考虑到第$i$个字符,短串中最多能匹配到第$j$个字符的方案数,那么答案就是$$\sum_{i=0}^{m-1} f[n][i]$$考虑如何从$f[i-1][k]$转移到$f[i][j]$:预处理一个数组$g[k][j]$表示短串中前缀...
September 29, 2019

CometOJ3978 天天背单词prefix

题意求总共$n$个单词中$k$个单词连成的字符串在所有可能的字符串中从小到大排序后的排名数据范围: 单词总长度$\le 10^6$,输入文件大小小于$2MB$题解因为数据保证不存在某个单词是另一个单词的前缀,所以直接对输入的单词进行排序,将其转化为数字那么输入的字符串自然是$1 \dots n$的数字中$k$个数字的排列,问题转化为计算这个排列的排名,例如样例5 3 a b c d e ca...
September 26, 2019

洛谷P2890/USACO07OPEN 便宜的回文Cheapest Palindrome

题意给出小写字母组成的字串,要求增删字母使其变为回文串,增删不同字母的花费不同,求最小花费数据范围:$1 \le L \le 2000$题解用$f[i][j]$表示将区间$[i,j]$修改为回文串的最小花费,显然有$$f[i][i]=0$$当$s[i]=s[i+1]$时有$$f[i][i+1]=0$$因为要从小区间转移到大区间,$f[i][j]$可以从$f[i+1][j]$或$f[i][j-...