注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河军团大本营

光荣的军团,永远的丰碑 <坚持原创>

 
 
 

日志

 
 

忽略大小写的kmp字符串匹配算法  

2012-08-29 19:03:42|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

  网上找到的kmp算法似乎都是区分大小写比较的,前些天研究了一下,发现可以将kmp算法方便地改成忽略大小写来比较,代码如下:

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

//据说来自于linux 2.6.14+内核的kmp算法

int is_ascii(char c)
{
return c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z';
}

int samechar_nocase(char a, char b)
{
return a == b || is_ascii(a) && is_ascii(b) && (a | 0x20) == (b | 0x20);
}

void kmp_init(const char *patn, int len, int *next)
{
int i, j;
assert(patn != NULL && len > 0 && next != NULL);
next[0] = 0;
for (i = 1, j = 0; i < len; i++){
while (j > 0 && !samechar_nocase(patn[j], patn[i]))
j = next[j -1];
if (samechar_nocase(patn[j], patn[i]))
j++;
next[i] = j;
}
}

int kmp_find(const char *text, int text_len, const char *patn,
int patn_len, int *next)
{
int i, j;
assert(text != NULL && text_len > 0 && patn != NULL && patn_len > 0
&& next != NULL);
for (i = 0, j = 0; i < text_len; i++){
while (j > 0 && !samechar_nocase(text[i], patn[j]))
j = next[j - 1];
if (samechar_nocase(text[i], patn[j]))
j++;
if (j == patn_len)
return i + 1 - patn_len;
}
return -1;
}

int main(int argc, char *argv[])
{
/* The code of you application goes here */
if (argc < 3) {
printf("Usage: %s text pattern\n", argv[0]);
return 1;
}

int *next;
int i, pos, len = strlen(argv[2]);

next = calloc(strlen(argv[2]), sizeof(int));
kmp_init(argv[2], strlen(argv[2]), next);
printf("next array:\n");
for (i = 0; i < len; i++)
printf("\t%c", argv[2][i]);
printf("\n");
for (i = 0; i < len; i++)
printf("\t%d", next[i]);
printf("\n");

pos = kmp_find(argv[1], strlen(argv[1]), argv[2], strlen(argv[2]), next);
printf("find result:\n");
if (pos < 0){
printf("None found!\n");
}else{
printf("%s\n", argv[1]);
for (i = 0; i < pos; i++)
printf(" ");
printf("^\n");
}

return 0;
}

  原始的kmp算法如下:

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

//据说来自于linux 2.6.14+内核的kmp算法

void kmp_init(const char *patn, int len, int *next)
{
int i, j;

assert(patn != NULL && len > 0 && next != NULL);
next[0] = 0;
for (i = 1, j = 0; i < len; i ++) {
while (j > 0 && patn[j] != patn[i])
j = next[j - 1];
if (patn[j] == patn[i])
j ++;
next[i] = j;
}
}

int kmp_find(const char *text, int text_len, const char *patn,
int patn_len, int *next)
{
int i, j;

assert(text != NULL && text_len > 0 && patn != NULL && patn_len > 0
&& next != NULL);
for (i = 0, j = 0; i < text_len; i ++ ) {
while (j > 0 && text[i] != patn[j])
j = next[j - 1];
if (text[i] == patn[j])
j ++;
if (j == patn_len)
return i + 1 - patn_len;
}

return -1;
}

int main(int argc,char *argv[])
{
/* The code of your application goes here */

if (argc < 3) {
printf("Usage: %s text pattern\n", argv[0]);
return 1;
}

int *next;
int i, pos, len = strlen(argv[2]);


next = calloc(strlen(argv[2]), sizeof(int));
kmp_init(argv[2], strlen(argv[2]), next);
printf("next array:\n");
for (i = 0; i < len; i ++)
printf("\t%c", argv[2][i]);
printf("\n");
for (i = 0; i < len; i ++)
printf("\t%d", next[i]);
printf("\n");

pos = kmp_find(argv[1], strlen(argv[1]), argv[2], strlen(argv[2]), next);
printf("find result:\n");
if (pos < 0) {
printf("None found!\n");
} else {
printf("%s\n", argv[1]);
for (i = 0; i < pos; i ++)
printf(" ");
printf("^\n");
}


return 0;
}

  以上代码在gcc中编译测试通过。

  评论这张
 
阅读(737)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018