请教两道面试题

我猜测你不会分析算法复杂度，是吧。呵呵。第二，其实我这个是迭代，我只是接着gigix的话，我的方法把问题的量级降低了很多。

第一，你的比较的方式是全部比较。比如每一个短信读进来的时候平均情况下要和一半已经读进来的短信进行比较，而且还是每个字符串都从头比到尾。

我的方法先hash，然后平均下来一个key只是对应100多个字符串，每个字符串需要对比的对象你想想有几个？（而且，我还可以进行二次hash），当然这个问题建立一个retrieve tree也不错，但是需要的比较次数也太多，而且额外空间太大。

貌似很正确的扯淡，很多语言内置的字符串匹配都是基于KMP算法

基数排序是非比较排序算法，算法的时间复杂度是O(n)。从表面上看具有不小的优势.但事实上可能有些出入，因为基数排序的n可能具有比较大的系数K，你可以看到这些短信是一行一条，数据项的规模不是很大，实际情况下短信一般也是几十个字符甚至几个字符，所以根本没必要用Radix Sort！

且不说什么效率，偶现在怀疑你设计的方法的健壮性，偶的方法简单明了，即使用面向对象的语言也可以轻松实现，那么你是否能给一个清晰的过程，而不是随便说说，什么hash，什么二次hash，什么retrieve tree，偶想知道你的准确的过程…………

/***
*strcmp.c - routine to compare two strings (for equal, less, or greater)
*
*       Copyright (c) Microsoft Corporation. All rights reserved.
*
*Purpose:
*       Compares two string, determining their lexical order.
*
*******************************************************************************/

#include <cruntime.h>
#include <string.h>

#ifdef _MSC_VER
#pragma function(strcmp)
#endif  /* _MSC_VER */

/***
*strcmp - compare two strings, returning less than, equal to, or greater than
*
*Purpose:
*       STRCMP compares two strings and returns an integer
*       to indicate whether the first is less than the second, the two are
*       equal, or whether the first is greater than the second.
*
*       Comparison is done byte by byte on an UNSIGNED basis, which is to
*       say that Null (0) is less than any other character (1-255).
*
*Entry:
*       const char * src - string for left-hand side of comparison
*       const char * dst - string for right-hand side of comparison
*
*Exit:
*       returns -1 if src <  dst
*       returns  0 if src == dst
*       returns +1 if src >  dst
*
*Exceptions:
*
*******************************************************************************/

int __cdecl strcmp (
        const char * src,
        const char * dst
        )
{
        int ret = 0 ;

        while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
                ++src, ++dst;

        if ( ret < 0 )
                ret = -1 ;
        else if ( ret > 0 )
                ret = 1 ;

        return( ret );
}

来，今天开完会，没事，专治各种信口开河。

对于不懂的东西，虚心一些，会死么？虽然我可以让你永远以为你算法很厉害，不过我很无聊，我决定用别的方式玩。

这个……那个……我前段时间看了下java中String的方法，他的匹配确实不是KMP的，我也不知道为啥……

偶说很多，没说所有，你最好再把python源码翻出来看看

拜托你不要转换话题，你先用你的算法把这个实现再去死也不迟，这个也是最主要的，整这个有啥用啊？

 

恩，既然老刑亲自来了，那么也设计个好的算法给偶学习下吧：），偶等着…………

我算法不匝地，不趟这个水了……
我只是说我不知道为啥java的String匹配不拿KMP算法做，应该是有原因的吧？

能给个java版的吗？这句没看明白：
        while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
                ++src, ++dst;

int
_PyString_Eq(PyObject *o1, PyObject *o2)
{
PyStringObject a = (PyStringObject) o1;
PyStringObject b = (PyStringObject) o2;
return Py_SIZE(a) == Py_SIZE(b)
&& *a->ob_sval == *b->ob_sval
&& memcmp(a->ob_sval, b->ob_sval, Py_SIZE(a)) == 0;
}

http://svn.python.org/projects/python/trunk/Objects/stringobject.c

需要继续治疗啊。

to JavaWHB:这段代码又不是他写的，估计他也不是很明白…………

to 老刑：java是不是kmp不重要，这里只是举个python perl的例子，重要的是你要搞明白，java的内置算法肯定是经过优化的，难道sun公司的人是吃白饭的？

这个题目是面试题，主要是说清楚你的思路，在真实的开发中和你拿个算法玩是2回事，关键的是你能拿出一套清晰可行的方案，再去扯什么效率的问题，我面试的时候最讨厌什么都是貌似什么凭感觉，概念满天飞，可行性呢？有几个公司花钱供你去研究理论算法的？