首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 互联网 >

探究一道字符串模式匹配有关问题

2013-10-27 
探究一道字符串模式匹配问题一 问题二 解题思路正如上图所示,采用一个辅助数组arr来记录字符串str中具有单

探究一道字符串模式匹配问题

一 问题

探究一道字符串模式匹配有关问题

二 解题思路

探究一道字符串模式匹配有关问题

正如上图所示,采用一个辅助数组arr来记录字符串str中具有单词的位置,例如单词WORLD确实出现在字符串str中,那么与之对应的arr区域都是1,那么扫描完arr,就可以输出 所有的单词。

三 运行结果

探究一道字符串模式匹配有关问题

四 代码

/* * 2014 weipinghui  xiaoyuan recruitment * a method of string pattern match*/#include <stdlib.h>#include <stdio.h>#include <string.h>#define SIZE 1024const char *dictionary = "hello,world";   // to define a pattern stringvoid StringToWord(const char *str) {int *arr;                  // to locate the targetchar tmp[SIZE];int i, j, k;int cnt;                  // the counter of matched stringint m;int start;int n = strlen(str);j = 0;arr = (int *)malloc(sizeof(int) * n);          memset(arr, 0 , sizeof(arr));for(i = 0;dictionary[i];i++) {if(dictionary[i] != ',') {tmp[j++] = dictionary[i];}/* * to get a string*/if(dictionary[i] == ',' || !dictionary[i + 1])  {tmp[j] = '\0';start = 0;/* * to match*/while(start < n) {const char *p = strstr(str + start, tmp);if(!p) break;   // there is no matchcnt = 0;m = strlen(tmp);k = p - str;    // wherer to startwhile(cnt < m) {arr[k++] = 1;cnt++;}start = p - str + strlen(tmp);}j = 0;}}for(i = 0;i < n;i++) {if(arr[i]) putchar(str[i]);}putchar('\n');free(arr);}int main() {char str[SIZE];gets(str);StringToWord(str);return 0;}

五 编程体会

    采用辅助空间是个小小技巧,但时间复杂数有点高哦。

热点排行