algorithm - 文本中最长的字符串

Question

我有以下 Java 代码:

import java.util.*;
public class longest{
public static void main(String[] args){
int t=0;int m=0;int token1, token2;
   String words[]=new String[10];
    String word[]=new String[10];
String common[]=new String[10];
   String text="saqartvelo gabrwyindeba da gadzlierdeba aucileblad ";
     String text1="saqartvelo gamtliandeba da gadzlierdeba aucileblad";
StringTokenizer st=new StringTokenizer(text);
StringTokenizer st1=new StringTokenizer(text1);

token1=st.countTokens();
token2=st1.countTokens();
while (st.hasMoreTokens()){

words[t]=st.nextToken();
  t++;
}
  while (st1.hasMoreTokens()){
     word[m]=st1.nextToken();
  m++;
}
 for (int k=0;k<token1;k++){
     for (int f=0;f<token2;f++){
      if (words[f].compareTo(word[f])==0){
  common[f]=words[f];
}
}
}
   while (i<common.length){
   System.out.println(common[i]);
   i++;
}
}
}

我希望在公共(public)数组中将元素放在文本或这些单词中

• saqartvelo(英语为格鲁吉亚)
• da(英语)
• gadzlierdeba(会更强)
• aucileblad(当然)

然后在这些单词之间找到具有最大长度但不能更正确地工作的字符串，它向我显示这些单词以及许多空元素。

如何纠正？

Answer 1

以下片段应该具有指导意义:

    import java.util.*;
    //...

    String text1 = "saqartvelo gabrwyindeba da gadzlierdeba aucileblad";
    String text2 = "saqartvelo gamtliandeba da gadzlierdeba aucileblad";

    List<String> common = new ArrayList<String>();
    for (String s1 : text1.split(" ")) {
        for (String s2 : text2.split(" ")) {
            if (s1.equals(s2)) {
                common.add(s1);
            }
        }
    }

    Collections.sort(common, new Comparator<String>() {
        @Override public int compare(String s1, String s2) {
            return s2.length() - s1.length();
        }       
    });

    System.out.println(common);
    // prints "[gadzlierdeba, saqartvelo, aucileblad, da]"

主要思想:

• 首选 List在数组上
  • 如果你事先不知道会有多少元素，这特别方便
• 首选 foreach
• StringTokenizer是遗留类；更喜欢String.split
• 使用自定义 Comparator和 Collections.sort用于对 List
进行排序

相关问题

• Sorting an ArrayList of Contacts (使用 Comparator 的好例子)
• Java Integer: what is faster comparison or subtraction?
  • 一般 int 的减法比较是错误的——小心使用!

---

另一种解决方案

请注意，上面的解决方案是 O(N^2)，因为它会检查每对单词以查看它们是否相等。这意味着当两个文本有很多单词时它不能很好地扩展。使用 Set，例如 HashSet，您可以在预期的 O(N) 时间内完成此操作，使用 Set.retainAll计算两个集合的交集。

static Set<String> wordSet(String text) {
    return new HashSet<String>(Arrays.asList(text.split(" ")));
}
//...

String text1 = ...;
String text2 = ...;

Set<String> commonSet = wordSet(text1);
commonSet.retainAll(wordSet(text2));

List<String> common = new ArrayList<String>(commonSet);
System.out.println(common);
// prints "[da, aucileblad, saqartvelo, gadzlierdeba]"
// in no particular order

// sort by string length using Comparator as above