最长的公共子串与恒定的内存？

给定两个字符串 - 如何使用常量内存找到最长的公共子字符串？最长的公共子串与恒定的内存？

更新：时间限制是解决它在O（len1 * len2），就像标准的动态编程解决方案。

2009-10-16 Frank

听起来像功课给我;放弃是“不变的记忆”。 – 2009-10-16 21:44:08

这就像“给出只有14个字节的内存可用，你如何实现一个快速排序算法”，或者是否有这种实际用法？至少，我会说，所需的内存量将取决于所涉及的字符串的长度，除非“常量”意味着“真正的大屁股数，没有人会需要”...... – 2009-10-16 21:44:39

但点作业的主要目的不是要问别人怎么做，而是要自己搞清楚，否则你就不会去了解为什么这是一件好事，或者在这种情况下是一个不好的解决方案。一种纯粹的蛮力方法，肯定会使用不断的记忆，会吸引驴子，就像没有明天一样。家庭作业问题的重点不在于获得答案，而在于理解那个答案是什么，以及理解答案是什么。在这种情况下，它不是一个好主意*。这就像教学一样，一把斧头尖锐，但不会告诉你为什么这可能是坏的。 – 2009-10-16 21:51:03

固定内存和没有时间限制？

只是做一个强力方法：比较所有的可能性，保持在内存中只有6整数索引：start和end两个字符串，加上2尚未发现的最长的字符串...

来源

2009-10-16 21:44:26 Seb

最长的公共子串与恒定的内存？

回答

相关问题