Eddie Chen


A Front-End Web Developer;

A fakegeek studying at Uestc;

A boy who loves the logic and structure of coding;


Resume

Project List

+

福州金玉堂网站

form 2011 - 2012

福州金玉堂企业网站开发

页面重构, jQuery开发, 基于Ajax的在线聊天子系统, 实时期货价格图表生成(基于Ajax&jsonp)

→ View website

+

diandian.com 数个模板开发

+

中国技术供需在线

form 2011 - 2012

中国技术供需在线-教育部全国高校产学研合作公共服务网络平台

负责一期项目后端开发, 数据库设计

基于PHP, CI框架开发

→ View website

+

电子科技大学校工会新版网站

2011

电子科技大学校工会新版网站

负责后台开发(PHP+CI)以及项目管理

→ View website

+

电子科技大学科技处网站

2010

电子科技大学科技处网站

负责部分页面重构

→ View website

Skill

HTML

80%

CSS & CSS3

70%

Javascript

80%

PHP

60%
*skill scores are based on the test provided by Elance.com.

Blog

恶补基础之数据结构学习笔记--串


前言


恶补基础进入第四天,进度还算不错,不过接着几天树和图部分应该比较折腾.串这一部分,前面朴素算法从简,重点看经典的KMP算法.KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此称之为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作,其基本思想是:每当匹配过程中出现字符串比较不等时,不需回溯指针,而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离,继续进行比较。

KMP算法

KMP算法可以大大避免重复遍历源字符串的情况, 其关键是next数组的生成. next[j]的定义:

next[j] = 0; (j = 1); next[j] = k; k 是使得子串i~k-1和子串j-k+1~j-1相等的最大k的值 next[j] = 1; 其他情况

KMP算法C实现

这里假定字符数组S,T的第0位置为字符串长度值.

//
//  main.c
//  KMP
//
//  Created by Eddie Chen on 5/11/13.
//  Copyright (c) 2013 Dreamfly. All rights reserved.
//

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

void get_next(char * T, int *next)
{
    int i = 1, j = 0;
    next[1] = 0;

    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i;
            ++j;
            next[i] = j;

        }
        else
            j = next[j];
    }
}

int KMP(char * S, char * T)
{
    int i = 1;
    int j = 1;
    int next[255];
    get_next(T, next);
    while (i <= S[0] && j <= T[0]) {
        if (j==0 || S[i] == T[j]) {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }
    if (j > T[0]) {
        return i - T[0];
    }
    else{
        return 0;
    }

}

int main(int argc, const char * argv[])
{

    char T[10] = " foobar";
    char S[50] = " thisisjustafootestforsearchingstringfoobar";
    T[0] = 6;
    S[0] = 42;
    int i = KMP(S, T);

    printf("%d", i);

    return 0;
}

总结

虽然看着书写出来个勉强能跑通的, 但是感觉还是没有很好的理解KMP算法的实质.继续往后看等对这些东西的思维跟上了之后再好好回来重新理解一次..


Date:

About

This is Eddie Chen, a front-end web developer, a member of Dreamfly Studio of UESTC.
Keep in touch:
haozi[a,t]haozi.name


Powered by Eddie Chen.