USACO/prefix

tips

对输入数据的元素集合有疑问的人，应该注意，断行后的上一行行末与新的一行开始的单词虽然没有空格隔开，但是算两个元素。

如果你被行末空格、字符读入不换行等等有关读入的问题搞得心力憔悴，代码变得难以改动，为什么不试试看读入到一个字符串中再处理？（如果要分割字符串，获得其中各元素的话可以自己动手写一个过程）

分析

动态规划

设dp[i]表示主串S中从i开始的最长的可组成的前缀，dp[1]就是所求，状态转移方程：

{dp[i]=max{dp[j]+j-i}|i到j-1的字串是primitive。 i<j<=n}

用Hash表判断primitive，将每个primitive转成10位2进制数，再mod一个大质数。在判断primitive的时候只需把i到j-1的字串的Hash值算出来就可以了。

因为primitive最多只有10位，所以时间复杂度是O(n)级别，其中n是主串的长度。

我补充一下，判断primitive时，也可以用kmp算法提前造一个表，表示主串中所有的字串，这样的时间复杂度（仅造表）为O（（m+n）*k），m为基本串长（可忽略），n为主串长，k为基本串个数，比hash较高，但很稳定。

---

另一个转移方程：f[i]表示s前i个字符能否取得 f[i]:=(f[i-length(p[j])]) and (copy(s,i-length[p[j]]+1,length[p[j]])=p[j]);

i:=length(s); j:=P集合中元素个数；

这个方程可以这样实现:对于当前位置i,枚举每个词典如果,f[i]=true且pipei(i,length(table[j]))=true,那么f[i+length(table[j])]=true.此时ans:=max(ans,i+length(table[j])).并且,循环条件有两个:i:=1..length(s)和i<=ans

初始化： fillchar(f,sizeof(f),false); f[0]:=true;

最后取得最大的值为真的f[ans]就行了 (当i>ans时即可break了)

［如果你WA了，请注意一下边界，特别是C语言的朋友］——一个因此WA了3次的人。

[用pascal的朋友，s请用字符数组或ansistring]

Trie

参见Trie.
源码

DFS

其实本题目还可以DFS，用那个集合中的元素去填充原序列中的元素，把添加最多的记录下来，注意优化： 1、可以进行剪枝，如当前匹配长度+最小元素长度>序列总长度时退出 2、用一点点动归思想，用一个布尔数组记录下当前的值是否DFS过，如果DFS了，直接退出 这样做可以达到达到大部分0.000s,详见我的代码(ID:hncsyjc3)

简单BFS

用一个堆栈记录可以达到的长度，见code#bfs

C++ STL

将一个字符串以一个较大的质数为因数降幂排列算出值，存入一个map（相当于红黑树），然后进行简单递推就行了，详见C++代码yc5-yc

参考代码

C
C++
Pascal
Java

引用

[1]

[2]