月度存档: 八月 2011

用C实现的一个简单的线程池

线程池文件有pool.c和pool.h,测试代码在test.c。测试代码比较乱,但应该足够看懂怎么用了。打包下载:pool.tar

pool.h

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <pthread.h>

#define MAX_THREAD 2000

typedef void *(*job_func)(void *);

typedef struct a_job {
    job_func func;
    void *arg;
    void **result;

    struct a_job *next;
} job;

typedef struct {
    pthread_t *workers;
    int total;
    int free;

    job *jobs;
    job *job_end;
    int jobc;

    pthread_mutex_t q_mutex;
    pthread_cond_t  q_cond;

    int init;
    int destroy;
} thread_pool;

int pool_init(int);
int pool_add_job(job_func, void *, void *);
int pool_destroy();
void *routine(void *);

pool.c


#include "pool.h"

static thread_pool *pool;

int
pool_init(int count)
{
    if (count > MAX_THREAD)
        return -1;

    if (pool != NULL)
        return 0;

    pool = (thread_pool *)malloc(sizeof (thread_pool));
    if (pool == NULL)
        return -1;
    memset(pool, 0, sizeof (thread_pool));

    pool->total = pool->free = count;
    pool->init = 1;
    pool->destroy = 0;
    pool->jobc = 0;

    pthread_mutex_init(&pool->q_mutex, NULL);
    pthread_cond_init(&pool->q_cond, NULL);

    pool->workers = (pthread_t *)malloc(sizeof (pthread_t) * count);
    if (pool->workers == NULL)
        return -1;
    memset(pool->workers, 0, sizeof (pthread_t) * count);

    int i;
    for (i = 0; i < count; i ++) {
        pthread_create(pool->workers + i, NULL, routine, NULL);
    }

    return 0;
}

int
pool_destroy()
{
    if (pool == NULL)
        return 0;
    if (pool->destroy == 1)
        return 0;

    pool->destroy = 1;
    pool->init = 0;

    pthread_cond_broadcast(&pool->q_cond);
    int i;
    for (i = 0; i < pool->total; i ++) {
        pthread_join(*(pool->workers + i), NULL);
    }

    free(pool->workers);

    pthread_mutex_destroy(&pool->q_mutex);
    pthread_cond_destroy(&pool->q_cond);

    free(pool);
    pool = NULL;

    return 0;
}

int
pool_add_job(job_func func, void *arg,  void *result)
{
    job *tmp_job = (job *)malloc(sizeof (job));
    if (tmp_job == NULL)
        return -1;
    tmp_job->func = func;
    tmp_job->arg = arg;
    tmp_job->result = result;

    pthread_mutex_lock(&pool->q_mutex);
    if (pool->job_end == NULL) {
        pool->jobs = pool->job_end = tmp_job;
    } else {
        pool->job_end->next = tmp_job;
        pool->job_end = tmp_job;
    }
    pool->jobc ++;
    tmp_job = NULL;
    printf("A job added, number of jobs : %d\n", pool->jobc);
    pthread_mutex_unlock(&pool->q_mutex);

    pthread_cond_signal(&pool->q_cond);

    return 0;
}

void *
routine(void *arg)
{
    pthread_cleanup_push(pthread_mutex_unlock, &pool->q_mutex);

    printf("Thread 0x%x start!\n", pthread_self());

    while (1) {
        pthread_mutex_lock(&pool->q_mutex);
        while (pool->jobc == 0 && pool->destroy != 1)
            pthread_cond_wait(&pool->q_cond, &pool->q_mutex);

        if (pool->destroy == 1) {
            pthread_mutex_unlock(&pool->q_mutex);
            printf("Thread 0x%x exit\n", pthread_self());
            pthread_exit(NULL);
        }

        job *tmp_job = pool->jobs;
        pool->jobs = pool->jobs->next;
        pool->jobc --;
        pthread_mutex_unlock(&pool->q_mutex);

        printf("Job run by thread 0x%x\n", pthread_self());

        if (tmp_job->result != NULL)
            *(tmp_job->result) = (*tmp_job->func)(tmp_job->arg);
        else
            (*tmp_job->func)(tmp_job->arg);
        free(tmp_job);
    }

    pthread_exit(NULL);
    pthread_cleanup_pop(0);
}

test.c


#include "pool.h"

void *
func(void *arg)
{
    int *a = (int *)malloc(sizeof (int));

    *a = *(int *)arg;

    sleep(1);
    return a;
}

int
main(int argc, char **argv)
{
    pool_init(3);

    printf("inited\n");

    int arg = 1;
    void *tmp;
    pool_add_job(func, &arg, &tmp);

    printf("add job finished\n");
//    sleep(5);

    printf("going to destroy\n");
    pool_destroy();

    printf("res is %d\n", *(int *)tmp);

    free(tmp);
    return 0;
}

python虚拟机实现(一)

python并不将py文件编译为机器码来运行,而是由python虚拟机一条条地将py語句解释运行,这也是为什么被称为解释语言的原因之一。但python虚拟机并不直接执行py語句,它执行编译py語句后生成的字节码。本篇简单地讲下编译、运行的过程,涉及到的内容有如何编译、控制流、函数及类的实现等。

0. python的编译

python将py文件编译成为PyCodeObject,再将这个对象写入某文件就成为了pyc文件,文件中包含python的magic number(来说明编译时使用的python版本号)、源文件的mtime(使pyc和py文件保持同步)、编译出的code对象。将对象写入到一个文件似乎听起来不太可能,不过其实很简单,python只写入特定类型的对象,比如要写入一个code对象,python会按一定的顺序将这个对象中的属性一一写入,由于对象是固定的,因而只要记下写入时的顺序就可以从文件中恢复出对象。注意我们这里谈论的并不是python中的序列化。python在写入实际的对象时会写入标识符,即可以标明对象的边界,又可以保持内容信息以在内存中恢复出对象。

python将对象写入文件最后会将调用到两个函数,一个用来写个int,一个用来写入string。对于string来说,为了达到和intern机制一样的目的不重复写string,在写入的时候python还会维持一个dict来保存已经写入的被intern处理后的string,因此当一个string被intern处理过并且出现在之前所说的dict中时,python仅仅会写入该string的索引值,即它是第几个string。当读取文件时,python则会根据每个string的索引值重建一个list,碰到重复的intern的string时就可以根据索引值读出该string的值了。

1. python虚拟机基础

python虚拟机的执行方式就是模仿普通x86可执行文件运行方式,也有栈、帧等概念。除止之外,python还有一个执行环境的问题,考虑print a句话,a肯定指向了一个对象,但是是什么对象呢,这个就由执行环境来确定了,語句可以通过执行环境读写变量的值,在源代码中对这个执行环境的模拟是对它PyFrameObject来完成的,每一个code block都对应一个执行环境,就是一个PyFrameObject,可以认为是一帧。这个struct比较复杂,看下代码:


typedef struct _frame {
    PyObject_VAR_HEAD
    struct _frame *f_back;	/* previous frame, or NULL */
    PyCodeObject *f_code;	/* code segment */
    PyObject *f_builtins;	/* builtin symbol table (PyDictObject) */
    PyObject *f_globals;	/* global symbol table (PyDictObject) */
    PyObject *f_locals;		/* local symbol table (any mapping) */
    PyObject **f_valuestack;	/* points after the last local */
    /* Next free slot in f_valuestack.  Frame creation sets to f_valuestack.
       Frame evaluation usually NULLs it, but a frame that yields sets it
       to the current stack top. */
    PyObject **f_stacktop;
    PyObject *f_trace;		/* Trace function */

    /* If an exception is raised in this frame, the next three are used to
     * record the exception info (if any) originally in the thread state.  See
     * comments before set_exc_info() -- it's not obvious.
     * Invariant:  if _type is NULL, then so are _value and _traceback.
     * Desired invariant:  all three are NULL, or all three are non-NULL.  That
     * one isn't currently true, but "should be".
     */
    PyObject *f_exc_type, *f_exc_value, *f_exc_traceback;

    PyThreadState *f_tstate;

    PyTryBlock f_blockstack[CO_MAXBLOCKS]; /* for try and loop blocks */
    PyObject *f_localsplus[1];	/* locals+stack, dynamically sized */
} PyFrameObject;

许多个PyFrameObject通过f_back连成一串链表,表示了帧与帧之间的先后、调用顺序。python中帧在运行时需要额外的内存,比如a = b + c这段代码,那么需要先请读入b、c,再算a,除此之外还有局部变量等需要保存在栈中,因此最后有一个f_localsplus指向这块多出来的内存,大小则在编译时计算出来保存在f_stacksize中,这块内存具体用来依次保存locals(局部变量)、cellvars、freevars(后两个和闭包的实现有关)、动态栈(f_valuestack指向栈底、起始位置,f_stacktop则维持栈顶)。

当Python虚拟机开始执行时,它会先进行一些初始化操作,最后进入PyEval_EvalFramEx函数,它的作用是不断读取编译好的字节码,并一条一条执行,类似CPU执行指令的过程。函数内部主要是一个switch结构,根据字节码的不同执行不同的代码。

2. Python运行环境及执行过程

先从整体上看看Python的运行环境。我们知道在操作系统中执行程序离不开两个概念:进程和线程,在Python中也是这样,Python模拟了这两个概念。模拟进程或线程的分别是PyInterpreterState和PyThreadState。可以想象,每个PyThredState都对应着一个帧栈,Python虚拟机在多个线程上切换。

当Python虚拟机开始执行时,它会先进行一些初始化操作,最后进入PyEval_EvalFramEx函数,它的作用是不断读取编译好的字节码,并一条一条执行,类似CPU执行指令的过程。函数内部主要是一个switch结构,根据字节码的不同执行不同的代码。用一张图表示:

3. Python的名字空间

名字空间在Python中是一个非常重要的概念,读写变量值其实就是到某个名字空间中读写与该变量名相对应的对象。如果我们把某个符号和与之关联的对象之间的关系(就是(name, value)这样的关联关系)称为約束的话,那可以认为名字空间的内容就是由一组组約束构成,而增加約束的語句可以被称为赋值語句,函数定义、类定义等都可以被称为是赋值語句。当一个module被加载后,Python会执行相应的代码在这个module的名字空间中建议相应的約束,然后就可以用module.attr这样的語句来访问module的属性。

对于每个module来说,它都有一个顶层的名字空间,可以认为是global名字空间,同时也没有哪个名字空间能够跨module存在。具体到module的某行代码,对它来说还存在local名字空间(比较在函数体或类定义中)、enclosing名字空间(用来实现闭包,其实它不真的存在,但假定有这样一个更好理解)。而Python内置了builtin名字空间。如果要查找某个符号的话,Python会依次查找LEGB。要注意的是Python具有静态作用域,它的意思就是说名字空间这个东西是在你写好py代码后就确定的,而不是由执行的时候确定的。这一部分对于理解Python非常重要,由于篇幅所限之前在是不能详述,建议查看《Python源码剖析》第8.2节。

python内置对象的实现

准备回顾一下python源代码,不过不准备说的太细,尽量勾勒框架,不引用代码。

0. python中对象的概念

python中所有东西都是对象,进一步地,这些对象可以分为类型对象(type)or实例对象,有时一个对象即可以是类型,也可以是实例。所有这些对象中,除了内置的类型对象外,别的都生存于堆上,内置的类型对象则静态分配内存。

每个对象头部都有一个PyObject_HEAD(其实对于某些需要被gc管理的对象,它的头部先为PyGC_Head,再为PyObject_HEAD)。变长对象在HEAD后还有一个ob_size表示变长对象元素个数的多少,非字节数。

类型的信息都在它的type对象里,源码中为struct _typeobject,也就是PyTypeObject。比如实例化一个类型,那会先找它的tp_new(找不到的话在父类找),在tp_new中根据该type的tp_basesize进行分配内存,再调用tp_init进行初始化。对类型的实例做运算,比如相加其实也是找type对象中相应的函数指针。type对象中的信息到后来基本都会在类型的dict中和相应的key对应起来。

1. int的实现

int比较简单,关键在于如何高效地实现。python首先有小整数对象。默认在[-5, 257)。如果超出范围则使用通用的缓冲池,对于大整数则有PyIntBlock,用来作缓冲池。一个block大小大概为1000个字节,去掉头部(8字节),可以存82个整数对象。block之间通过指针相连,首指针为block_list,free_list则维护着一条可以链表,free_list链表的下一项由未用的PyIntObject的ob_type来维持。

一些细节:当无可以用缓冲池可用时python会调用fill_free_list来创建一个新的block,并将其插入block_list,再把free_list指向这个block的objects中的最后一个元素。当某个block中的某个int被释放时,它将自己的ob_type指向free_list,并修改free_list等于它的地址,其实就是一个头部插入,这样把多个block间的objects数组联系起来防止出现内存泄漏。一个值得注意的地方是小整数对象池其实也是生活在block里面,在是整个python环境初始化的时候生成。这里可以看出,为int分配的内存是永远也不会被python释放的,所有的int对象使用的内存大小和同时存在的int数量的最大值有关。

2. string的实现

string复杂一些,它是变长对象。对变长对象内存的管理。每个string对象除了头部外还保存了hash值(ob_shash,避免重复计算,初始-1)、是否已经被intern机制处理过(ob_sstate)、指向实际内存的指针(ob_sval),ob_sval指向的应该是一段ob_size+1长度的内存(为了兼容C,字符串要以'\0'结尾)。在从char *创建string时还是比较直接的,就是检查一些边界情况、初始化hash等,最后逐个拷贝char。python中有一个nullstring指向空字符串,通过intern机制共享,所以不会同时存在多个空字符串。

传统缓冲池。相当于int小整数缓冲池,对单个的char,python也会维持一个缓冲池。创建单个char的string时,如果缓冲池里已有,则直接返回。如果没有,根据char创建string,再对它进行intern,再存入缓冲池。

intern机制。python会维持一个dict,用来保存当前已经被创建的string,如果新创建的string已经在这个dict,也就是已经被intern机制处理过了,那么就会直接返回dict中的值。也就是说一般两个相同的字符串的id是相同的。要注意的是,无论字符串有没有存在于这个dict中,python都会创建一个新要string,原因是因为保存在dict中只能是PyObject,因此肯定要创建一个python对象。intern后的string有两种状态,mortal和immortal,区别在于后者永远不会被gc回收。

要提到的是,创建string时使用的是PyObject_Malloc开头的分配函数,一般来讲它不会每次都从os分配内存,而是从python维持的一个内存池中分配。

3. list的实现

list不仅是变长对象,还是可变对象。在变长头部之外PyListObject还保存了一个PyObject **ob_item指针,一个int allocated。ob_item就是指向实际成员的指针,allocated代表了list当前申请的内存能装多少个PyObject,变长头内的ob_size则代表list中已有多少个PyObject。当创建一个list时,需要指定list的大小(参数size),要申请的内存可以分为两部分,一个是list本身,一个是指向成员变量的指针。如果list缓冲池可用(numfree > 0),那就从缓冲池中给list分配一块内存,否则使用PyObject_GC_NEW来分配空间(和string不同,因为list中的成员可以指向其它python对象,这个函数和python垃圾回收的三色标记法有关)。然后再根据size大小分配一段连续的内存来保存指向各个成员的指针,新创建的list中的ob_size和allocated都为size。

创建list后给list里的某个位置赋值比较简单,就是简单的設定指针而已。添加操作要复杂一些,首先会调整list的大小,使得allocate>=size>=allocate/2。如果该等式已经满足,那么不更改list大小,如果不满足的话通过new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize得出新的allocated大小,再通过PyMem_Resize来调整保存成员指针的内存。resize后则使用最简单的策略移动从插入到结尾的成员指针,再设置该位置上的成员。删除成员时实际删除后的也要进行resize操作,和插入时类似。实际删除的操作则由list_ass_slice来实现,它有两种用法,一是更改list中的某一段为特定的值,另一种就是删除list中的某一段。list中每删除一个元素都会造成内存拷贝。一个值得注意的细节是由于从list中删除或是更改的对象需要减少引用计数,但减少引用计数时又会循环调用一些list函数,可能会造成list索引值的破坏,因而函数中得用一个temp数组保留从list中剥离的成员,等删除工作完成,list结构已经确定的情况下再逐一减少其引用。

当list被销毁时,对其成员逐个减少引用,然后检查缓冲区是否已经满,如果没有的话就将该list放入缓冲区,这样下次再创建list的时候就不用为list对象本身再分配对象了。

4. dict的实现

python中的dict是用hash表实现,解决冲突的方法是开放定址法,即二次探测,删除时使用伪删除技术(顺便说下在一致性假设下,如果用k来表示hash表的使用率的话,那么一次成功查找需要的比较次数为1/k * ln(1/(1-k)),插入时的比较次数最多为1/(1-k))。

在一个dict中,每个(key,value)对组成一个entry,entry中还另外存储了key的hash值。对每个entry来说有三种状态unused(key,value皆为NULL,初始状态),active(key,value不为NULL,存储了元素),dump(对应于伪删除技术,key=dummy,value=NULL)。dict实际上就是entry的集合,定义如下:

typedef struct _dictobject PyDictObject;
struct _dictobject {
	PyObject_HEAD
	Py_ssize_t ma_fill;  /* # Active + # Dummy */
	Py_ssize_t ma_used;  /* # Active */

	/* The table contains ma_mask + 1 slots, and that's a power of 2.
	 * We store the mask instead of the size because the mask is more
	 * frequently needed.
	 */
	Py_ssize_t ma_mask;

	/* ma_table points to ma_smalltable for small tables, else to
	 * additional malloc'ed memory.  ma_table is never NULL!  This rule
	 * saves repeated runtime null-tests in the workhorse getitem and
	 * setitem calls.
	 */
	PyDictEntry *ma_table;
	PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
	PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

PyDict_MINSIZE一般被设为8。使用PyDict_New来创建一个新dict时,其实就是分配相应的内存,将ma_fill,ma_used设为0,ma_mask设为7(8-1),ma_table指向ma_smalltable,ma_lookup默认为lookdict_string。在实现dict时python也使用了缓冲池,方法和list基本一样。

ma_lookup这个函数指针确定了散裂函数和冲突发生时的二次散裂函数,在dict中进行搜索有两种方法,lookdict_string和lookdict,后一种是更一般的方法。由于python中dict用的非常广泛,而这些dict中大多数key都是string,因而专门提供了一个搜索方法来进行加速,其实两种方法的本质都是一样的。搜索的具体过程如下:1. 获得探测链中当前应该检测的entry;2. 如果是unused状态,那搜索失败,应该返回一个可用的(可以被设置值)的entry,所以如果freeslot不为空(之前找到了dummy态的entry)就返回freeslot指向的entry,否则返回当前entry;3. 如果entry为dummy态且freeslot未设置,则设置freeslot,继续查找下一个;4. 依次检查当前entry的key和查找的key是否引用相同、值相同,若不是继续查找下一个。需要注意的是,dict使用哪种方法进行查找取决于待查找的key,如果是string的话则利用lookdict_string,和本身已经有的entry中的key无关。

dict的插入和删除基于之前的搜索,很好理解。当插入时先搜索该key,得到一个entry,再根据它的状态来修改它达到插入的上目的。删除操作也类似。需要注意的是插入元素的时候,会检查ma_fill/(ma_mask+1)是否大于2/3,如果装载率的确大于这个值并且有unused或dummy的entry被填充的时候,就会调整dict的大小,新的大小最小为minsize=ma_userd*(ma_used>50000?2:4),显然改变dict大小会造成内存移动,因此这时候可以丢弃dummy的entry。新的dict大小从8开始逐次*2增长,直到大于minsize。接下来就是一些初始化动作,逐个检查entry并插入新的dict等。

开始使用amazon ec2

由于某些众所周知的原因,到我空间22端口的连接总是被timeout,justhost不提供修改端口功能(提供了就出鬼了),实在是不能忍了,决定弄个vps,试了试ec2,本来是准备花钱的,后来发现居然可以免费一年,我就用来fq总是够用了,算是意外之喜。并且新加坡的机房ping值不到200,比以前空间的300多要好多了。

注册很简单,就是要注意填手机号的时候不要加86,我就是因为加了86,最后输pin码时手动改了手机号結果使pin码一直不对。

开始使用前以为会比较复杂,結果发现我想太多了= =…,免费的基本只有用自带的AMI+micro plan+On-Demand Instances。没有什么别的选择机会。这里有个教程可以看看,http://www.giroro.com/amazon-ec2-study-notes-1/,注意登陆的时候的用户名是ec2-user,好囧。。

最后吐槽一下。。AMI是在CentOS的基础上改的,我只很久前用过一段时间的CentOS,各种操作都不会了有木有。就不能来个Debian/Ubuntu or Arch之类的吗。。。我们小用户不用那么高稳定性的。。。

程序员面试题精选100题的答案合集和一些常用算法

最近在为找工作做些准备,做了些题看了些算法,其中有一个程序员面试题精选100题好像是比较有名的(现在还没出满100题),我把自己的答案放上来,如果有人来讨论一下那更好了。我是用的C来做题,有些C++ only的题就跳过了。还有一些别的算法比如RMQ的st解法,kmp等代码都在里面。打包下载地址在这里jingxuan.tar.gz

顺便有几个算法想单独地说一下:

1. O(n)时间求最长回文。主要思路就是从第一个字符开始扫描,记录下以当前字符结尾的最长回文长度。代码如下

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

int
find(const char *s)
{
    if (!s)
        return -1;

    int lens = strlen(s);

    int i, same = 1, pre = 1, max = 0;
    for (i = 1; i < lens; i ++) {
        int l = 0, s1;
        s1 = i - pre - 1;
        if (s1 >= 0 && *(s + s1) == *(s + i))
            l = pre + 2;

        if (l == 0)
            l = *(s + i - 1) == *(s + i) ? 2 : 1;

        if (*(s + i) == *(s + i - 1))
            same += 1;
        else
            same = 1;

        s1 = l > same ? l : same;
        if (s1 > max)
            max = s1;

        pre = s1;
    }

    return max;
}

int
main(int argc, char **argv)
{
	printf("%d\n", find("aaa"));
	printf("%d\n", find("goooog"));
	printf("%d\n", find("guouyy"));

	return 0;
}

2. 怎么在O(n)的时间,O(1)的空间找出一串数字中两个不同的只出现一次的数字(别的都出现两次)。这题普遍一点的解法是用位数组,不过还可以考虑把整个数组分成两个子数组,每个分别含有一个只出现一次的数字。代码如下


#include <stdio.h>
#include <assert.h>

int n1, n2;

int
find_once(int array[], int length)
{
    assert(length > 0);
    assert(array != NULL);

    int all = 0, pos = 0, i = 0;
    unsigned int tmp;

    for (i = 0; i < length; i ++)
        all ^= array[i];
    assert(all != 0);

    tmp = (unsigned int)all;
    pos = (tmp - (tmp & (tmp - 1)));

    for (i = 0; i < length; i ++) {
        if (array[i] & pos != 0)
            n1 ^= array[i];
        else
            n2 ^= array[i];
    }

    return 0;
}

int
main(int argc, char **argv)
{
    int a[10] = {1, 2, 1, 2, -1, -1, 3, 3, 0, -4};

    find_once(a, 10);
    printf("%d %d", n1, n2);

    return 0;
}

3. 全排列、组合、幂集算法,分重复不重复两种情况(待添加)

4. 后缀数组(待添加)

5. kmp算法(见上一篇博文)

kmp算法及简单应用

kmp算法是模式匹配中的经典算法,在处理很多和字符串的问题时都会用到。不过这个算法虽然实现起来很简单,思路想要描述清楚却不容易,网上有很多资料,但感觉都讲的不太清楚,有些代码都是错误的。为了验证自己已经弄清楚了,决定从头开始介绍这个算法。

假定T为待匹配的文本,P为模式。假定T为ababaabcbab,P为ababaca。我们先从T的第一个字符开始匹配起,粗体表示匹配失败的字符

T a b a b a a b c b a b
P a b a b a c

如果按照朴素的匹配算法,那我们下次应该就从第二个字符开始匹配。那有没有更快一些的方法呢?观察一下P,前两个字符分别和第三、第四个字符相等,也就是说如果我们下次可以从T的第1+2,也就是第三个字符开始匹配起。也就是说假定P[1...q] = T[s + 1...s+q],那么满足P[1...k]=T[ss + 1... ss + k] 的ss最小是多少,其中ss + k = s + q。

进一步地解释,假定匹配在T的第t位和P的第p位失效了,那么我们接下来要继续比较T的第t位和P的(p-x)位,相当于把P往右移了x位。那么如果我们能知道p-x的值,整个匹配过程就很好理解了,t每次增大1,当匹配失效时置p为p-x,继续匹配。

如何知道p-x的值呢?我们先考察一下它的意义,匹配失败并重置p为p-x后我们可以继续比较T的第t位和P的p-x位,这说明在这位之前,t的长为p-x-1的左串等于P的长为p-x-1的前缀。事实上这就是p-x的定义。对于所有的p,记其p-x的值为向量next。那么给定P,对于其中的第i位来说,如果P[i-k+1...i]和P[1...k]相等,且k < i,则next[i] = k。

求next向量的过程可表示如下,先初始化next[0]为0,假设我们已经知道next[i-1] = k,求next[i]。
1. 如果P[k + 1] = P[i],则next[i] = k + 1
2. 如果P[k + 1] != P[i] 并且 k > 0,则令k = next[k] 直到P[k + 1] = P[i]或 k = 0
3. 第2步得到了新的k,如果P[k + 1] = P[i],那么next[i] = k + 1,否则为k。

完整代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define MAX 10000

void
gen_next(char *p, int *next)
{
    int len = strlen(p);

    *next = 0;
    int k = 0;
    int i = 1;

    for (i = 1; i < len; i ++) {
        while (k > 0 && *(p + k) != *(p + i))
            k = *(next + k);
        if (*(p + k) == *(p + i))
            k ++;
        *(next + i) = k;
    }

    // We can set next[0] to -1 to make the code simpler
    // *next = -1;
}

int
find(char *p, char *q)
{
    assert(p && q);

    int *next, lenq = strlen(q), lenp = strlen(p), count = 0;
    next = (int *)malloc(sizeof (int) * lenq);
    if (next == NULL)
        return -1;
    memset(next, 0, sizeof (int) * lenq);

    gen_next(q, next);

    int pi, qi;
    pi = qi = 0;
    while (pi < lenp && qi < lenq) {
        // If next[0] == -1, the while loop can be writen is this way
        //
        // if ((*(p + pi) == *(q + qi) || qi == -1) && pi < lenp && qi < lenq)
        //     pi ++, qi ++;
        // else
        //     qi = *(next + qi);
        while (*(p + pi) == *(q + qi) && pi < lenp && qi < lenq)
            pi ++, qi ++;
        if (qi == lenq) {
            printf("found one match, begins at %d\n", pi - lenq);
            count ++;
            qi = *(next + qi - 1);
            continue;
        }
        if (qi == 0) {
            pi ++;
        }  else {
            qi = *(next + qi);
        }
    }

    return count;
}

int
main(int argc, char **argv)
{
    char s[MAX] = "ababab";
    char p[MAX] = "abab";

    printf("total %d match\n", find(s, p));

    return 0;
}