一道百度算法笔试题，大家讨论讨论
音节{a,ab,bc,abc}
输入：abcab
找出最大的音节顺序，保证都匹配。
如上述最大的应该为：a-bc-ab
------------------------------------------
这种匹配算法应该是怎么样一个思路呢？？？
工作这么多年，很少做算法优化的工作，这次被BS，只能说自己没有头脑风暴过啊。。。


[解决办法]
用Trie应该可以（基本上相当于分词），LZ说说更细的要求吧！
[解决办法]
只想到动态规划
以abcab为例，
记某字符串s的最大匹配为F(s)
从开始搜索，发现可以匹配a,ab,abc
那么结果应该是
F(abcab)=max{1+F(bcab),1+F(cab),1+F(ab)}
估计实现起来有点小复杂。。。

探讨

引用:

最大的音节顺序？
这个是何意？
abc-ab这个匹配为啥不行
引用:
音节{a,ab,bc,abc}
输入：abcab
找出最大的音节顺序，保证都匹配。
如上述最大的应该为：a-bc-ab
------------------------------------------
这种匹配算法应该是怎么样一个……

[解决办法]
如果串中有未能匹配的字符怎么处理？
比如{a,ab,bc,abc}，串是adabbc，另外{a,ada}，串是ada，应该算匹配了一个ada还是匹配了2个a？

确认了规则之后，其实并不复杂，用Trie + DP就行，以前做过类似的题目。

探讨

那个两个分块，最多应该3个分块的