这个算法的minimaze时间复杂度（在feed中选择常见的子串）

我有一个非常大的coloumns feed文件。我会represennt一个字符串coloumns之一，我要检查这些字符串...这个算法的minimaze时间复杂度（在feed中选择常见的子串）

让我们看看我们这些字符串值（在coloumn），进料显然是finctional :)：

"Gia Joe Black Viper" 
"Street Fighter...Ken" 
"Mortal Kombat, Scorpion" 
"Gia Joe Desert Fox" 
"Mortal Kombat, Sub Zero" 
"Street Fighter...Ryu"

我想找到字符串中的匹配...所以简化任务是：找到字符串的子串的一个在另一个字符串，并到HashSet收集这些子......

所以basicaly的结果标签为：

Gi Joe 
Mortal Kombat 
Street Fighter

我写了一个简单的代码来测试算法，但我想最小化这个任务的时间复杂度，空间复杂性不如时间重要...（您可以认为饲料像10.000行一样，所以它是基数有时间复杂度低）你可以找到和我下面的代码阅读：

String[] stringArray = new String[6]; 
     stringArray[0] = "Mortal Kombat - Scorpion"; 
     stringArray[1] = "Street Fighter - Ken"; 
     stringArray[2] = "Mortal Kombat - Scorpion"; 
     stringArray[3] = "Gi Joe - Desert Fox"; 
     stringArray[4] = "Gi Joe - Desert Dog"; 
     stringArray[5] = "Street Fighter - Ryu"; 

     HashSet<String> commonStrings = new HashSet(); 

     for (int i = 0; i < stringArray.length; i++) { 
      String[] splittedString = stringArray[i].split("[ ]"); 
      System.out.println("i"+i); 
      for (int j = 0; j < stringArray.length; j++) { 
       System.out.println("j"+j); 
       String matchable = ""; 
       for (int k = 0; k < splittedString.length; k++) { 
        System.out.println("k"+k); 
        if(k==0)matchable=matchable; 
        else {matchable = matchable + " " + splittedString[k];} 
        if(j!=i){ 
         System.out.println("StringArray["+j+"]("+stringArray[j]+")index.of("+matchable+")"+"is"+matchable.indexOf(stringArray[j])); 
         if (stringArray[j].indexOf(matchable) > 0) { 
          commonStrings.add(matchable); 
         } 
        } 
       } 
      }

赞赏，使我的代码更好的任何建议，谢谢！

来源

2012-08-22 czupe

有关Java约定的副作用：变量应以小写字母开头：'StringArray' =>'stringArray'。 – assylias

你有权利，我只是试图快速与代码...编辑。 – czupe

你在寻找整个单词还是字母的任何部分。 –

你的复杂性是二次的，可以通过使用包含HashMap这样是O（N）：

Map<String, Integer> cout = new HashMap<String, Integer>(); 

for (String line : StringArray) { 
    for (String s : line.split("-")) { 
    Integer currentCount = counts.get(s); 
    if (currentCount == null) 
     counts.put(s, 1); 
    else 
     counts.put(s, currentCount + 1); 
    } 
} 
//Look in currentCount all keys with a value larger than 1.

这仍然可以优化（但不会降低复杂性）通过提高else声明）。

来源

2012-08-22 12:49:09 jolivier

好的，谢谢你，我的代码仍然不完美，因为我看到了，我将改变它...但也需要降低复杂性... – czupe

您可以对单词进行拆分和排序，而不是遍历此类排序列表。结果应该是一样的。当然，这只是整个单词检查的解决方案。您可以使用一些专用数据结构而不是排序。

来源

2012-08-22 12:50:16 czajek

是的，我可以definietly排序之前迭代整个饲料！好主意... – czupe

这个算法的minimaze时间复杂度（在feed中选择常见的子串）

回答

相关问题