一道算法题极其让人摸不到头脑

Question

我给个想法看看：
   1、 先判断是不是回文，如果不是
   2、取其长度，从字符串的一半＋1（姑且称它为shalf）开始检测
   3、看shalf距离为一的字符是不是相同
   4、如果相同比较shalf距离为2的字符，依次执行，如果到字符串长度都相同则只要在符串后面加上前面的倒序就可以了
      
   5、如果不同比较将shalf加1，重复3，4，如果加到sharf等于字符串的长度，怎么办你也知道了:)

Answer 1

it is so hard for me
up

Answer 2

这实际上是一个最长相同子序列(LCS)问题 的应用而已决定最少插入次数的关键因素是 当前字符串的左右匹配度
对于Ad3ad这样的字符串， 从左到右依次以每个字符分割判断左右字符串，用LCS算法算出最长共同子串 需要检查的所有字符对为：{(A,3ad) (Ad,ad)(Ad3,d)} 考虑到可能回文可能具有偶数个字母， 还要加上以空格为分隔符那些字符对 ：（A,d3ad） (Ad,3ad) (Ad3,ad) (Ad3a,d) 把所有的LCS值比较一下，具有最大值的就是具有最小插入次数的匹配方法。 接下来就是根据最小匹配子串填出一个最后结果了这种方法时间效率不是很高，希望有人能有优化的方法 ：）

Answer 3

同意 huangry(凯撒)。
但这样的查找下去，时间效率不高，继续期盼……

Answer 4

huangry(凯撒)的算法应该是对的，关注。

Answer 5

其实复杂度还算可以， 比N*N*lgN要低很多， 更何况只不过5000的数据。
不过总觉这个问题应该有比较巧妙的方法

Answer 6

我提供程序：
public void anagram(String word){    int numofChars=word.length();
    if(numofChars==1){ }
    else{
       for(int i=1;i<=numofChars;i++){
           char firstLetter=word.chatAt(0);
           suffix=word.substring(1,numofChars);
           anagram(suffix);           word=suffix+firstLetter;
        }
       }
     }

Answer 7

好像刚才不太对，真不好意思，我从写了一个
public String huiwen(String word){
 
     int length=word.length();
     char contain[length]={};
     
     for(int i=length-1;i>0;i--){
          int ptr=0;
          contain[ptr]=word.charAt(i);
          ptr++;
       }
      return (word+contain);
}

Answer 8

This type of job can be done by Perl.
If you know diff, this problem is not hard.Give you an idea:Ad3ad1.reverse
  da3dA
2. LCS between original and reverse
  "d3d" or "dad"
3. Symmetrically insert
 ***
   d3d --- > Ad3ad
   0a (A), 2a (a);  // 0a (A): add 'A' to "d3d" at position 0
   
   Symmetrically insert:
   0a (A) -- 3a (A) ---> Ad3dA;  //  3 = "d3d".length() - 0
   2a (d) -- 1a (d) ---> Ada3adA; // 1 = "d3d".length() - 2, positions are refer 
                                  // to source string "d3d"
    
 ***
   dad --> Ad3ad
   0a (A), 1a (3);  
   
  Symmetrically insert:
   0a (A) -- 3a (A)  --> AdadA
   1a (3) -- 2a (3)  --> Ad3a3dA4.results
  Ad3a3dA or Ada3adAmost LCS can only return one result, d3d or dad, not both. That's enough.This algo is optimal.code should be easy to you.
   
   

Answer 9

huangry(凯撒) 
这位兄弟不是已经做出来了么

Answer 10

CSDN社区将于2004年10月1号开始进行强制结帖，结帖对象是发帖时间在2004.1.1--2004.6.30之间的未结帖子。
说明：
1、强制结帖的首要目的是减小数据库容量，提高服务器的性能、速度
2、强制结帖可能会历时几天，这期间社区的访问速度可能会较慢（具体现象可能是操作超时等），请大家谅解
3、每个未结帖子被强制结帖后，扣除发贴人信誉分1分，帖子的分数回归系统，并不平均分给回复人
4、0分帖被强制结帖后，不扣信誉分
5、请大家在10月1号前及时结帖，以免造成不必要的损失；由于不及时结帖造成的损失，csdn不作补偿，比如信誉分减少等。查看自己是否有未结帖的方法：
请打开页面左边的导航条，点击“我的社区”－》“我的问题”，已结帖的标题前应该是绿色的小勾；如果不是请点右边的“管理”，发帖时间在2004.1.1--2004.6.30之间的请结帖。还不会结帖的网友请看http://www.csdn.net/help/over.asp