标签: longest-prefix

对于一个相对微不足道的问题,提出最优雅的JavaScript,Ruby或其他解决方案是一项挑战.

此问题是最长公共子字符串问题的更具体情况.我只需要在数组中找到最长的公共起始子字符串.这大大简化了问题.

例如,最长的子串[interspecies, interstelar, interstate]是"inters".但是,我不需要找到"ific" [specifics, terrific].

我已经通过快速编写JavaScript解决方案来解决这个问题,作为我关于类似shell的选项卡完成的答案的一部分(这里是测试页面).这是解决方案,略有调整:

function common_substring(data) {
  var i, ch, memo, idx = 0
  do {
    memo = null
    for (i=0; i < data.length; i++) {
      ch = data[i].charAt(idx)
      if (!ch) break
      if (!memo) memo = ch
      else if (ch != memo) break
    }
  } while (i == data.length && idx < data.length && ++idx)

  return (data[0] || '').slice(0, idx)
}

此代码在此Gist中提供,以及Ruby中的类似解决方案.您可以将gist克隆为git repo来试用它: …

我需要有关任何标准python包的信息,这些包可用于URL上的"最长前缀匹配".我已经通过两个标准包不见了http://packages.python.org/PyTrie/#pytrie.StringTrie&"http://pypi.python.org/pypi/trie/0.1.1",但他们似乎并没有对URL的最长前缀匹配任务有用.

例如,如果我的设置包含以下网址1-> http://www.google.com/mail,2-> http://www.google.com/document,3-> http://www.facebook.com等等..

现在,如果我搜索"http://www.google.com/doc",则应返回2并搜索"http://www.face"应返回3.

我想确认是否有任何标准的python包可以帮助我这样做,或者我应该实现Trie的前缀匹配.

我不是在寻找一种正则表达式的解决方案,因为随着URL数量的增加它不可扩展.

非常感谢.

Problem Description: References: Fun With Strings

Based on the problem description, a naive approach to find sum of length of LCP for all possible substrings (for a given string) is as follows :

#include <cstring>
#include <iostream>

using std::cout;
using std::cin;
using std::endl;
using std::string;

int lcp(string str1, string str2) 
{ 
    string result; 
    int n1 = str1.length(), n2 = str2.length(); 

    // Compare str1 and str2 
    for (int i=0, j=0; i<=n1-1 && j<=n2-1; i++,j++) 
    { 
        if (str1[i] != str2[j]) 
            break; 
        result.push_back(str1[i]); …

我需要找到n个字符串中最长的公共子字符串,并在我的项目中使用结果.

java中是否有现有的实现/库已经这样做了？

感谢您提前回复.

如果我有一个私有IP地址块,如171.58.0.0/12,这是否意味着我基本上按位和32位版本171.58.0.0与32位1,其中最后12个为0 ,获取该范围内可接受的私有IP地址的最长前缀？

10101011.00111010.00000000.00000000 (171.58.0.0) AND
11111111.11111111.11110000.00000000 (12 bit mask?)

=

10101011.00111010.00000000.00000000 (Longest Prefix of Private IP addresses)

获取前缀可接受的私有IP地址？

谢谢!