字符串核对

字串核对

一、说明

今日的一些高阶程式语言对于字串的处理支援越来越强大（例如Java、Perl等），不过字串搜寻本身仍是个值得探讨的课题，在这边以Boyer- Moore法来说明如何进行字串说明，这个方法快且原理简洁易懂。

二、解法

字串搜寻本身不难，使用暴力法也可以求解，但如何快速搜寻字串就不简单了，传统的字串搜寻是从关键字与字串的开头开始比对，例如 Knuth-Morris-Pratt 演算法字串搜寻，这个方法也不错，不过要花时间在公式计算上；Boyer-Moore字串核对改由关键字的后面开始核对字串，并制作前进表，如果比对不符合则依前进表中的值前进至下一个核对处，假设是p好了，然后比对字串中p-n+1至p的值是否与关键字相同。

如果关键字中有重复出现的字元，则前进值就会有两个以上的值，此时则取前进值较小的值，如此就不会跳过可能的位置，例如texture这个关键字，t的前进值应该取后面的3而不是取前面的7。

三、代码
#include <stdio.h>

#include <stdlib.h>

#include <string.h>void table(char*); // 建立前进表

int search(int, char*, char*); // 搜寻关键字

void substring(char*, char*, int, int); // 取出子字串

int skip[256];

int main(void) {

char str_input[80];

char str_key[80];

char tmp[80] = {'\0'};

int m, n, p;

printf("请输入字串：");

gets(str_input);

printf("请输入搜寻关键字：");

gets(str_key);

m = strlen(str_input); // 计算字串长度

n = strlen(str_key);

table(str_key);

p = search(n-1,str_input,str_key);

while(p != -1) {

substring(str_input, tmp, p, m);

printf("%s\n", tmp);

p = search(p+n+1,str_input,str_key);

}

printf("\n");

return 0;

}

void table(char *key) {

int k, n;

n = strlen(key);

for(k = 0; k <= 255; k++)

skip[k] = n;

for(k = 0; k < n - 1; k++)

skip[key[k]] = n - k - 1;

}

int search(int p, char* input, char* key) {

int i, m, n;char tmp[80] = {'\0'};

m = strlen(input);

n = strlen(key);

while(p < m) {

substring(input, tmp, p-n+1, p);

if(!strcmp(tmp, key)) // 比较两字串是否相同

return p-n+1;

p += skip[input[p]];

}

return -1;

}

void substring(char *text, char* tmp, int s, int e) {

int i, j;

for(i = s, j = 0; i <= e; i++, j++)

mp[j] = text[i];

tmp[j] = '\0';

}

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。

发表于 2021-09-16 16:48
阅读 ( 520 )
分类：C/C++开发

字符串核对

你可能感兴趣的文章

相关问题

0 条评论

作家榜 »