最長的公共子串與恆定的內存？

給定兩個字符串 - 如何使用常量內存找到最長的公共子字符串？最長的公共子串與恆定的內存？

更新：時間限制是解決它在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

最長的公共子串與恆定的內存？

回答

相關問題