找出最长公共前缀 找出最长公共前缀

不会武功的猪 发布于 2015/07/19 12:01
阅读 3K+
收藏 0
$arr = ['abcdef','abcdea','abacdde','abbadf'];  等10W个单词,找到最长公共前缀 这里的最长的是ab
加载中
0
中山野鬼
中山野鬼
用最简单的方式,一个个的代入比较就可以了。分组并不好。哈。
0
B
BlueWoods

1. 先把每个字符串分解成一个前缀列表; 比如 abbadf, 可以分解得到 a, ab, abb, abba, ... abbadf;

2. 得到的所有的前缀列表拉平连在一起,组成一个新的列表,然后排序;

3. 然后计算每一个前缀出现的次数;

4. 然后从长到短找出现次数为n的前缀,就可以答案;

假设字符最长为m,那么可以分解出m - 1个前缀码,所以得到的前缀码列表长为 n * m; 排序(n * m) log(n * m); 计数 n * m. 应该比直接计算要快一些。

0
不会武功的猪
不会武功的猪

引用来自“BlueWoods”的评论

1. 先把每个字符串分解成一个前缀列表; 比如 abbadf, 可以分解得到 a, ab, abb, abba, ... abbadf;

2. 得到的所有的前缀列表拉平连在一起,组成一个新的列表,然后排序;

3. 然后计算每一个前缀出现的次数;

4. 然后从长到短找出现次数为n的前缀,就可以答案;

假设字符最长为m,那么可以分解出m - 1个前缀码,所以得到的前缀码列表长为 n * m; 排序(n * m) log(n * m); 计数 n * m. 应该比直接计算要快一些。

没明白呢。。。是否可以用PHP 解一下。
0
大汉刺史
大汉刺史
C语言跟你写一个你看看。
//求最长的公共前缀。
char *xtqz(char **arr,unsigned int length)
{

  unsigned int i=0;//指示应该匹配第i个字符串
  unsigned int j=0;// 指示应该匹配第j个字符
  char tmp1; //第一个字符串的第j个字符
  char *result=NULL;//返回的结果 也就是公共前缀
  unsigned int length2=strlen(arr[0]);//控制匹配字符的次数

  for(;j<length2;j++)
  {

     tmp1=*(arr[0]+j);//得到第一个字符的第j个字符,用来跟后面的字符串的第j个字符匹配

	 for(i=1;i<length;i++)
	 {
		 if(j>=strlen(arr[i]))//也许第一个字符串长度不是最短的,如果有比它更短的就应该退出匹配
			 break;

	    if(*(arr[i]+j)!=tmp1) //如果当前字符串的第j字符与第一个字符串的第j个字符不匹配就退出
			break;

	 }

	 if(i!=length)//这就是匹配失败后的情况
		 break;  

  }

  if(j>0)
  {
	result=(char *)malloc(sizeof(j+1)); //匹配第j个失败,所以就分配j+1个内存
   strncpy(result,arr[0],j);//复制第一个字符串的前j个到结果并把末尾价格\0
   result[j]='\0';
  }


return result;
}

int main()
{
 
 
	char *arr[] = {"abcdef","abcdea","abccdde","abcbadf"};
 
	printf("%s",xtqz(arr,4));
 
 
 return 0;
}



0
inuxor
inuxor

就一个一个来,跑一遍就完了,这玩意还有什么鬼神莫测的办法不成?


0
guerlab
guerlab
用二分法查找 效率比for高得多
大汉刺史
大汉刺史
回复 @骨二 : 你扯犊子吧,你说的匹配难道不需要一个字符一个字符的匹配。如果你使用字符串匹配函数,归根接底还是字符匹配。 另外,二分查询是对一组有序的的数组进行查找的算法。你这样不能叫二分法
guerlab
guerlab
先去前半段去匹配 如果成功 选择前3/4匹配 失败选择前1/4匹配 逐渐缩小范围 比用for的逐个匹配的时间复杂的上要小点儿
大汉刺史
大汉刺史
你怎么个二分法?不循环怎么比较每一个字符串
0
Erroooooor
Erroooooor
该评论暂时无法显示,详情咨询 QQ 群:点此入群
0
负心杏

前提:取最长公共前缀

零:循环求最短单词

一:假设最短单词为最长前缀

二:循环所有单词匹配前缀

三:如果有不匹配的,最短单词末尾去一个字母,继续第二步

四:当循环完毕,最短单词剩下的就是公共前缀了。


0
wensenfeng
wensenfeng

trie树解法:

/**
     * 使用trie树
     */
    private static class Trie{

        private Node root;
        private int max = 0;
        private int stringLength = 0;
        private String strings = "";
        private class Node {
            int count;
            Node[] next;
            public Node() {
                this.count = 0;
                next = new Node[57];
            }
        }

        public void put(String string) {
            root = put(root, string);
        }

        private Node put(Node node, String chars) {
            if (node == null) node = new Node();
            Node p = node;
            this.stringLength += 1;
            for (int i = 0; i < chars.length(); i++) {

                int id = chars.charAt(i) - 'A';
//                System.out.println("id: " + id + " char: " + chars.charAt(i));
                if (p.next[id] == null) {
                    p.next[id] = new Node();
                }
                p.next[id].count += 1;
                p = p.next[id];
            }
            return node;
        }

        public String getMax() {
            getMax(root);
            return this.strings;
        }

        private void getMax(Node node) {

            Node p =  node;
            for (int i = 0; i < 57; i++) {
                if (p.next[i] != null && p.next[i].count == stringLength) {
                    char c = (char) (i + 'A');
                    strings += c;
                    getMax(p.next[i]);
                    break;
                }
            }
        }
    }

    /**
     * @param strs: A list of strings
     * @return: The longest common prefix
     */
    public String longestCommonPrefix(String[] strs) {

        if (strs == null || strs.length == 0) {
            return "";
        }

        Trie t = new Trie();
        for (String s : strs) {
            t.put(s);
        }
        return t.getMax();
    }



0
wensenfeng
wensenfeng
/**
     * 另一种解法,两个两个的比
     * @param strs
     * @return
     */
    public String longestCommonPrefix2(String[] strs) {

        if (strs == null || strs.length == 0) {
            return "";
        }

        if (strs.length == 1) {
            return strs[0];
        }

        String ret = minCommonPrexString(strs[0], strs[1]);
        for (int i = 2; i < strs.length; i++) {
            ret = minCommonPrexString(strs[i], ret);
        }
        return ret;
    }

    /**
     * 得到两个字符串最长的公共前缀长度
     * @param str1
     * @param str2
     * @return
     */
    private String minCommonPrexString(String str1, String str2) {

        if (str1 == null || str2 == null || str1 == "" || str2 == "") {
            return "";
        }

        int len1 = str1.length();
        int len2 = str2.length();
        int min = Math.min(len1, len2);
        int ret = 0;
        for (int i = 0; i < min; i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                return str1.substring(0, ret);
            }
            ret += 1;
        }
        return str1.substring(0, ret);
    }



OSCHINA
登录后可查看更多优质内容
返回顶部
顶部