探究一道字符串模式匹配问题 - c++编程基础

一 问题

二解题思路

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

四代码 [cpp] /* * 2014 weipinghui xiaoyuan recruitment * a method of string pattern match */ #include #include #include #define SIZE 1024 const char *dictionary = "hello,world"; // to define a pattern string void StringToWord(const char *str) { int *arr; // to locate the target char tmp[SIZE]; int i, j, k; int cnt; // the counter of matched string int 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 match cnt = 0; m = strlen(tmp); k = p - str; // wherer to start while(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; } 五编程体会采用辅助空间是个小小技巧，但时间复杂数有点高哦。