首页 > 代码库 > 字符串总结

字符串总结

字符串总结

字符串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自动机:

后缀数组:


(未完待续)