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

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

题意：

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

思路:

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

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

树打的标记便自增1；

L： Obsession

题意：

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

思路：

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