月度归档：一月 2010

KMP算法

发表于 由
回复

KMP算法是字符串匹配的一种改进算法，在1977年由D. E. Knuth，J. H. Morris和V. R. Pratt一起提出，并以他们名字的首字母命名。和朴素的模式匹配算法相比，KMP算法最大的特点就是主串指针不回溯。它利用已经得到的“部分匹配”信息来减少不必要的比较而加快字符串的匹配速度。

KMP算法的本质

KMP算法本质上是实现了对自动机的模拟。它通过构造一个有限自动机来搜寻某给定的模式在正文中出现的位置。整个算法的核心就是对自动机的构建（或前缀函数的构建，KMP算法不用计算变迁函数，而是根据模式预先计算出一个辅助函数next来实现更快速的状态切换），当完成有限自动机的构建之后对主串的搜寻就显得很简单了。

前缀函数next的构建

模式的前缀函数包含有模式与其自身的位移进行匹配的信息。这些信息可用于避免在朴素的模式匹配算法中对无用位移的测试。比如主串和模式串在主串指针为Ti、模式串指针为Pj处匹配失败时，可以主串指针不回溯并直接取next函数的值next[j] = k将模式串向右滑动到第k个字符处重新开始比较，而不用去做无用位移的测试。只是这样的操作能成立k必须要满足一定的条件，如下所示：

首先，如果模式串能直接向右滑动到第k个字符处重新开始比较则说明模式串中的前k-1个字符必然已经和主串匹配了，也即必然已经有下面式子，且为了能最大化的向右移动则不能存在更大的k’满足下面式子：
继续阅读 →

朴素模式匹配算法

发表于 由
回复

朴素模式匹配算法又称简单匹配算法或Brute-Force算法，它是字符串模式匹配中比较简单的一种算法。它从主串的第一个字符开始进行模式匹配，依次比较主串和模式串中的每个字符，若比较全部相等（模式匹配成功），则返回模式串中第一个字符在主串中的位置，否则主串指针从比较失败的字符处回溯到第二个字符开始重新和模式串进行匹配，这样依此下去，直到和模式串匹配成功或到主串的末尾（匹配不成功）为止。

朴素模式匹配算法的C/C++代码实现：

// 定义一个字符串结构体
typedef struct  {
    char data[MAX_SIZE];
    int length;
} string;

int BruteForce(string s, string t)
{
    int i = 0, j = 0;
    while (i < s.length && j < t.length) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1; // 主串指针回溯
            j = 0;
        }
    }

    if (j > t.length)
        return i - t.length;
    else
        return -1;
}

继续阅读 →

字符串函数

发表于 由
回复

几个常见字符串处理函数

/* *
 * str开头的函数部分
 * In the following functions,
 * variables s and t are of type char *;
 * cs and ct are of type const char *;
 * n is of type size_t;
 * and c is an int converted to char.
 */

/* strcpy - copy string ct to string s,
 including '\0'; return s. */
char *strcpy(char *s, const char *ct)
{
    char *tmp = s;

    while ((*tmp++ = *ct++) != '\0')
        /* nothing */;
    return s;
}

/* strcat - concatenate string ct to end of string s;
 return s. *
char *strcat(char * s, const char * ct)
{
    char *tmp = s;

    while (*tmp)
        tmp++;
    while ((*tmp++ = *ct++) != '\0')
        /* nothing */;

    return s;
}

/* strcmp - compare string cs to string ct,
 return <0 if cs<ct, 0 if cs==ct, or >0 if cs>ct. */
int strcmp(const char *cs,const char *ct)
{
    register signed char __res;

    while (1) {
        if ((__res = *cs - *ct++) != 0 || !*cs++)
            break;
    }

    return __res;
}

/* strlen - return length of cs. *
size_t strlen(const char *cs)
{
    const char *tmp;

    for (tmp = cs; *tmp != '\0'; ++tmp)
        /* nothing */;
    return tmp - cs;
}

/**
 * mem开头的函数部分
 * The mem... functions are meant for manipulating
 * objects as character arrays; the intent is an
 * interface to efficient routines.
 * In the following functions, s and t are of type void *;
 * cs and ct are of type const void *; n is of type size_t;
 * and c is an int converted to an unsigned char.
 */

/* memcpy - copy n characters from ct to s, and return s. */
void *memcpy(void *s, const void *ct, size_t n)
{
    char *dst = (char *)s, *src = (char *)ct;

    while (n--)
        *dst++ = *src++;

    return s;
}

/* memmove - same as memcpy except that it works even
 if the objects overlap. */
void *memmove(void *s, const void *ct, size_t n)
{
    char *dst, *src;

    if (s <= ct) {
        dst = (char *)s;
        src = (char *)ct;
        while (n--)
            *dst++ = *src++;
    } else {
        dst = (char *)s + n;
        src = (char *)ct + n;
        while (n--)
            *--dst = *--src;
    }

    return s;
}

/* memcmp - compare the first n characters of cs with ct;
 return as with strcmp. */
int memcmp(const void *cs, const void *ct, size_t n)
{
    const unsigned char *su1, *su2;
    signed char res = 0;

    for( su1 = cs, su2 = ct; 0 < n; ++su1, ++su2, n--)
        if ((res = *su1 - *su2) != 0)
            break;
    return res;
}

/* memset - place character c into first n
 characters of s, return s. */
void *memset(void *s, char c, size_t n)
{
    char *xs = (char *)s;

    while (n--)
        *xs++ = c;

    return s;
}