C語言KMP匹配算法的實現

KMP算法是用于字符串模式匹配的一種無回溯算法,其算法時間複雜度爲O(m+n)。其基本思路如下:

首先分析模式字符串p = “p0p1p2p3…pi…pk…pk+i-1pk+ipk+i+1…”

如果已知                         p0= pk, p1= pk+1, …, pi = pk+i                             (1)式

那麽,當pk+i+1匹配失敗時,可以直接右移字符串p,使得pi對齊pk+i的位置,pi及其之前的字符就不用再次匹配也能保證能夠匹配成功。而且,爲了不遺漏匹配成功的可能性,還要求對 “p0…pk+i”不存在更大的 i 及相應更小的 k 使得 (1) 式成立,否則會錯誤地將p字符串右移過長距離。

一般地,對字符串p的任意字符pr,存在一特定下標 k( r ),使得p0…pk( r )-1,與 pr-k( r)…pr-1是 pr 之前部分字符串的最長相同前後綴。在匹配過程中,當pr和源字符串中某字符匹配失敗時,可直接用pk( r )與之比較。

源代碼如下:

 

/* 字符串KMP快速匹配實現 */
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SRC_LEN 100
#define MDL_LEN 20

void makeNext(const char * szModel, int * next, int len);
void match(const char * szSrc, const char * szModel, int * index);

int main(void)
{
	char src[SRC_LEN];
	char mdl[MDL_LEN];
	int  len;
	int  index;

	puts("請輸入源字符串:");
	gets(src);
	puts("請輸入模式字符串:");
	gets(mdl);

	len = strlen(mdl);
	match(src, mdl, &index);
	printf("%d", index);
	getchar();
	return 0;
}

/* 匹配函數。通過index返回相匹配的字符串首字符在源字符串中的位置,
   通過返回值返回相匹配的字符串首字符的地址。若無相匹配的字符串,則
   index爲-1,並返回空指針NULL
 */
void match(const char * szSrc, const char * szModel, int * index)
{
	char * des;
	int	srcIndex = 0;
	int mdlIndex = 0;
	int srcLen = strlen(szSrc);
	int mdlLen = strlen(szModel);
	/* 創建next數組,並初始化 */
	int *next = (int *)malloc(mdlLen * sizeof(int));
	makeNext(szModel, next, mdlLen);
	
	/* 匹配主循環體 */
	while (mdlIndex < mdlLen && srcIndex < srcLen) {
		/* 若對應位置字符匹配則步進1,否則移動szModel */
		if (mdlIndex == -1 || szSrc[srcIndex] == szModel[mdlIndex]) {
			mdlIndex++; srcIndex++;
		} else {
			mdlIndex = next[mdlIndex];
		}
	}

	/* 若mdlIndex未達到串尾,表明szModel未完成匹配。否則即是完成匹配 */
	if (mdlIndex >= mdlLen) {
		*index = srcIndex - mdlLen;
	} else {
		*index = -1; 
	}
}

void makeNext(const char * szModel, int * next, int len)
{
	int index = 0;
	int k = -1;
	next[0] = -1;

	/* 掃描szModel字符串以確定next數組 */
	while (index < len) {
		while (k >= 0 && szModel[index] != szModel[k])
			/* 若不匹配,則移動字符串,同match函數 */
			k = next[k];
		index++; k++;
		/* !!!ATTENTION!!! */
		if (szModel[index] == szModel[k]) {
			next[index] = next[k];
		} else {
			next[index] = k;
		}		
	}
}
更多相關文章
  • C語言基于GTK+Libvlc實現的簡易視頻(二)
  • usb滑鼠_字符串及語言ID請求的實現8
    開發環境:win7開發板    :51單片機 + pdiusbd12 芯片前言:    字符串描述符(string descriptor)含有描述符性文字.有些字符串描述符可含有指向描述制造商,産品,序列號,配置,接口的字符串的索引.主機通過發送Get Descriptor 請求,且使設置事務中wV ...
  • 易語言界面庫的實現(一)
          易語言IDE自帶了界面庫,是通過"支持庫(DLL)"來提供的.脫離這些庫,你想寫自己的界面程序? 易畢竟不是C.沒有Win32 SDK .從常量到API聲明.光這些工作就能把你累個差不多.      以前也寫過一個界面庫.不過自己不是很滿意.易語言寫界面庫.首要考慮的 ...
  • 經常在筆試和面試中,公司會出一些C語言的庫函數讓面試者去做,這些函數看上去很簡單,其實還是要考慮很多的.下面就幾個常用的函數做一些簡單的實現.1.字符串複制函數//字符串賦值函數 char *strcpy( char *strDestination, const char *strSource ) ...
  • 觀察者模式的簡單概念 假設現在有A.B.C.D等四個獨立的對象,其中B.C.D這三個對象想在A對象發生改變的第壹時間知道這種改變,以便做出相應的回應.上面的這種情形,就是觀察者模式.當然每個被觀察者可以有多個觀察者,每個觀察者也可以有多個被觀察者.觀察者與被觀察者也不是對立的,壹個對象可以觀察其他對 ...
  • 文章來自:http://www.cnblogs.com/lifuqing/archive/2011/08/20/List.html #include "stdafx.h" #include "stdio.h" #include #include "s ...
  • 打開includds/init.php1. 將以下粘貼代 碼到 require (ROOT_PATH .  'languages/'  .  $_CFG [ 'lang' ] .  '/common.php'); 上面  if(!empty($_REQUEST['lang'])){  $_SESSI ...
  • #include "stdio.h" int main() { int a[10]; int i,j; for(i=0;i<10;i++) { scanf("%d",&a[i]); } for(i=0;i<9;i++) for(j=0;j& ...
一周排行
  • -MoPaaS應用開發大賽簡單網盤
    應用名稱:綠茶網盤 示例賬號:friend@me.com,密碼:wellcome 應用UR ...
  • 1         故障類型l  實例故障由ORACLE內部異常.操作系統故障或其它相關軟件引起,導致ORACLE實例中的進程或記憶體區出現故障或數據庫無法正常關閉,這種故障稱爲實例故障.實例故障沒有本質上的破壞,無 ...
  • Android 開發者必備的十大開發工具
    Android SDK提供了一系列可幫助開發者設計.創建.測試和發布Android應用程序 ...
  • Description 給出N個數,要求把其中重複的去掉,只保留第一次出現的數. 例如,給出的數爲1 2 18 3 3 19 2 3 6 5 4,其中2和3有重複,去除後的結果爲1 2 18 3 19 6 5 4.I ...
  • public static void main(String[] args) { List l = new ArrayList<>(); l.add("張三 "); l.add(&qu ...
  • private IDepartmentDao DepartmentDao;//只改departmentDao 不成 public IDepartmentDao getDepartmentDao() { return ...
  • GWT筆記(6) Java仿真(Java Emulation)盡管完整的GWT應用程序能用Java寫出,再部分被翻譯成JavaScript用于客戶端執行.但這裏有幾個不足:1)面向客戶端的代碼被某java包所限制,只 ...
  • 1.什麽是Rsync-Rsync配置參數詳解 Rsync(remote synchronize)是一個遠程數據同步工具,可通過LAN/WAN快速同步多台主機間的文件.Rsync使用所謂的"Rsync算法&q ...
  • 解決ADT大量出現Unexpected value from nativeGetEnabledTa
    安裝了最新版的Android SDK (r21) 和ADT 21.0.0,在虛擬機運行程序 ...
  • 1.錯誤描述freemarker.core.ParseException: Encountered "string" at line 21, column 21 in type.ftl. Was ...