相关疑难解决方法(0)

为了找到将给定字符串转换为回文所需的最小插入次数,我找到了字符串(lcs_string)及其反向的最长公共子序列.因此,要进行的插入次数是length(s) - length(lcs_string)

知道要插入的数量,应该采用什么方法来找到等效的回文串？

例如 :

1)azbzczdzez

所需插入次数:5 Palindrome字符串:azbzcezdzeczbza

虽然同一根弦可能存在多个回文弦但我只想找到一个回文？

问题:

给定任何字符串,添加尽可能少的字符,使其成为线性时间的回文.

我只能想出一个O(N ²)解决方案.

有人可以用O(N)解决方案帮助我吗？