谢卿云-2022010910017-字符串专题报告

B： 我承认阁下的字符串匹配很强

题意：

含有通配字符串的匹配问题;

思路:

采取暴力搜索文本串的思路；

假设当前搜索的位置为$$dfs(pos)$$,比较该位置往后的$$patlen$$个位置,观察是否能匹配，若能，便右移$$next$$个位置，若不能便右移一个位置，注意右移$$next$$个位置未必比右移一个位置更优，转移方程为$$dfs(pos)=max(dfs(pos+1),dfs(pos+next)+1)$$；

$$next$$是指模式串最长的前缀等于后缀的长度；

C： Necklace

题意：

找到字符串$$T$$所在的循环群字典序最小元；

思路：

循环群每一个元实际上都可以用原串的一个下标表示，因此无需复制；

比较不需要全串比较，只需要跳过前面相同的部分，比较第一个不同的字母即可；

暴力枚举所有的字符串，保持$$best$$的位置的更新；

C：Trap-Sirrom-Tunk

题意：

给定模式串与文本串，求解文本串的匹配次数；

思路：

$$KMP$$算法模板题；

找到模式串的$$next$$数组，考虑从前往后暴力遍历匹配，如果匹配失败则右移$$next$$个位置，否则答案自增1；

J: 数据攻防1

题意：

给定若干模式串，找到在文本串中出现的次数；

思路：

$$AC$$自动机模板题；

将每个模式串插入$$trie$$中，建立$$fail$$指针，遍历文本串，每次经过模式串在$$trie$$

树打的标记便自增1；

L： Obsession

题意：

在字符串末尾增加字符使得原串成为周期的；

思路：

利用$$KMP$$算法找到$$next$$数组，并且利用数组找到最佳的周期，如果原串是周期的倍数但是不等于周期，说明答案为0，否则，将原串补为最近的周期的倍数即可；