紧急！！！另一个单词对比的问题

Question

本帖最后由 maiah 于 2012-01-27 18:09:15 编辑

Answer 1

可以用kmp算法试试
public class kmp{
 public static void main(String[] args)
 {
  String a = "aaabcabcdeadfskdljfa;lskjdf;kljsdkjfeilskjf";
  String b = "abcabcde";
  int c = kmp_find(a,b,0);
  System.out.println(c);
 }
 static int[] GetNext(String fidStr)
 {
  int len = fidStr.length();
  int next[] = new int[len];
  int j = -1, i = 0;
  next[0] = -1;
  while(i < len-1)//这里这个减1是必要的，因为i关系到了要算出next的前一个
  {
   if(-1 == j || fidStr.charAt(j) == fidStr.charAt(i))
   {
    ++i; ++j;
    if(fidStr.charAt(j) == fidStr.charAt(i))
     next[i] = next[j];
    else
     next[i] = j;
   }
   else
   {
    j = next[j];
   }
  }
  return next;
 }
 static int kmp_find(String SurStr, String FidStr, int pos)
 {
  int next[] = GetNext(FidStr);
  int j = 0;
  int i = pos;
  while(j < FidStr.length() && i < SurStr.length()-FidStr.length()+1)
  {
   if(-1 == j || FidStr.charAt(j) == SurStr.charAt(i))
   {
    j++; i++;
   }
   else
   {
    j = next[j]; 
   }
  }
  if(j == FidStr.length())
  {
   return i-FidStr.length();
  }
  else
  {
   return -1;
  }
 }
}
--------------------------------------------------------------------------------

Answer 2

感觉楼主你是不是之前发过两个类似的帖子？下面这个程序，可以按照你的要求比较，而且允许乱序，本质上就是集合减法运算：public class TextCompare {    public static void main(String[] args) throws Exception {
        System.out.println(checkOnlyOne("trobato", "troato"));
        System.out.println(checkOnlyOne("troato", "trobato"));
        System.out.println(checkOnlyOne("nnice", "nmice"));
        System.out.println(checkOnlyOne("mice", "nmice"));
        System.out.println(checkOnlyOne("mice", "ecima"));
        System.out.println(checkOnlyOne("mice", "mice"));
    }    public static boolean checkOnlyOne(String a, String b) {
        int ca = minus(a,b).size();
        int cb = minus(b,a).size();
        return (ca + cb == 1);        
    }
    
    public static List<Character> minus(String base, String minus) {
        List<Character> cb = toChars(base);
        List<Character> cm = toChars(minus);
        List<Character> ret = minus(cb, cm);
        //System.out.println(ret);
        return ret;
    }    private static List<Character> minus(List<Character> base, List<Character> minus) {
        List<Character> ret = new ArrayList<Character>();
        ret.addAll(base);
        for (Character c : minus) {
            for (int i = 0; i < ret.size(); i++) {
                if (ret.get(i).equals(c)) {
                    ret.remove(i);
                    break;
                }
            }
        }        return ret;
    }    private static List<Character> toChars(String str) {
        List<Character> ret = new ArrayList<Character>();
        char[] cs = str.toCharArray();
        for (char c : cs) {
            ret.add(c);
        }
        return ret;
    }
}
结果：
true
true
false
true
true
false

Answer 3

兄台好思路，不过如果一个单词很长而且尽是xzy之类的话，基本上是不可行的了，会有溢出的。其实用一个32位的整数来表示一个单词即可，将32位的底26位每一位映射为一个字母，然后可以将每个单词中那些字母对应的位置1，会得出一个32位的整数了，顺下的就是比较整数的技巧了。

Answer 4

7楼和8楼的就别吵了，楼主要的内容，字母会重复的，没注意楼主的举例是：trobato？
所以你们的招数都存在一定的问题。

Answer 5

lz表达的问题本身就不是很清楚：到底是要两两比较还是前后循环比较？
“这样前面那个单词其实是包括后面那个单词的”我只取了这句话来讨论的，lz其他的要求不理解，直接无视了。另“前后单词相同，但是后面那个单词比前面那个单词多一个字母或者少一个字母”这句话我抓破脑袋也没整明白，求明白人翻译一下。“相同”了为什么还要有“但”？

Answer 6

解决没 刚看到你的问题，自己做了下 解决了（应该有更好的方案）
附我的思路：先把文件中的内容读入到字符串数组中，然后再循环比较数组中的元素判断依据：
1.后面和前面字符相同，但后者比前者多一个字符或者少一个字符 就是说前面字符contains后面字符
或者后面字符contains前面字符，前面字符比后面字符长1或者短1就是我if里面判断的条件伪代码如下：String str="";
         try {
BufferedReader bf = new BufferedReader(new FileReader("D:\\1.txt"));
String s ="";

while((s=bf.readLine())!=null){

//;
str+=s+"_";
//
}
bf.close();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

//System.out.println(str);
String[] strArray=str.split("_");
//System.out.println(strArray.length);
for(int i=0;i<strArray.length;i++){
//System.out.println(strArray[i]);
for(int j=0;j<strArray.length-i;j++){
if((strArray[j].contains(strArray[j+1])||strArray[j+1].contains(strArray[j]))&&(((strArray[j].length()+1)==strArray[j+1].length())
||((strArray[j].length()-1)==strArray[j+1].length()))){
//return true;
System.out.println("true");
}
else{
System.out.println("false");
return;
}
}

Answer 7

楼主可以把我上面的方法封装一下，因为我直接在main()函数中验证的，最好是把我上面的代码独立出来，供其他
地方调用会看起来整洁些。