首页 > 代码库 > 字符串总结
字符串总结
字符串总结
字符串hash：
Trie：
LA 3942：Remember the Word
题意：给定给出一个有S个不同单词组成的字典和一个长字符串。把这个字符串分解成若干个单词的连接（单词可以重复使用），有多少种方法？ 解题报告
UVa 11732：strcmp() Anyone?
题意：输入n个字符串，两两调用一次strcmp()，问字符比较的总次数是多少？ 解题报告
KMP：
LA 3026：Period
题意：给定一个长度为n的字符串s，求它每个前缀的最短循环节。对于每个i（2<=i<=n)，求一个最大的整数k>1（如果k存在），使得s的前i个字符组成的前缀是某个字符串重复k次得到。输出所有存在k的i和对应的k。
思路：首先根据kmp的方式求得next数组，然后我们可以发现，如果i-next[i] | i，那么就是一个循环节代码
扩展KMP：
poj 1699：Best Sequence
题意：给定一些字符串，如果一个字符串的后缀与另一个字符串的前缀相同，可以拼接，问经过拼接之后，可以组成的最短的字符串的长度。
思路：用扩展KMP预处理出每两个字符串的最大拼接值，然后DFS搜索最小值即可。 代码
串的最小表示法：
HDU 2609：How many
题意：给定一些长度相同的字符串，若两个字符串能够经过循环同构得到，则两者视为同一个字符串，问有多少种不同的字符串。
思路：将每一个字符串表示为最小表示法，然后排序，去重，即为答案。 解题报告
AC自动机：
后缀数组：
（未完待续）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。