暴力搜索最终版本。有两个错误、一个是我创建的buf缓存数组、没有每次用时重新初始化,导致有垃圾数据。
一个是我把闭区间[a ,b] 的大小算成了 b - a,这是计算[a, b)半开区间的方法。改正后如下
- #import <stdio.h>
- #import <string.h>
- int findLCS(char *s1, char *s2, char **s, char **e);
- int main(int argc, const char * argv[]) {
-
- // 解法1 暴力枚举法(两个字符串),反复调用即可求多个。
- char * s = NULL, *e = NULL;
- char *s1 = "nbitheimanb", *s2 = "mbitheib";
- findLCS(s1, s2, &s, &e);
- for (char *p = s; p <= e; p++)
- putchar(*p);
- puts("");
- return 0;
- }
- // 返回最大子串的大小,s记录最大子串的起始位置,e记录最后一个位置
- // 原本想用C++来写,比较简练,但是要求用C。
- int findLCS(char *s1, char *s2, char **s, char **e) {
-
- int len1 = strlen(s1), len2= strlen(s2);
- char buf[100] = {0};
- int max = -1; // 记录最大子串的大小
- char *str = NULL;
- char *p = len1 > len2? s2 : s1; // 指向两个串中最小串的第一个字符
- if (p == s1) str = s2; else str = s1; // 最大子串肯定在最小两个串中,所以枚举它的位置进行判断即可。
- for (char * ps = p; *ps; ps++) {
-
- for (char * pe = ps; *pe; pe++) {
-
- int len = pe - ps + 1; // 计算枚举的子串大小
- memset(buf, 0, sizeof(buf));
- strncpy(buf, ps, pe - ps + 1);
-
- if (strstr(str, buf)) { // 查找是否存在该子串
-
- if (len > max) {
-
- max = len;
- *s = ps; // 记录新的最大子串起始位置
- *e = pe; // 结束位置
- //printf("max = %d\n", max);
- }
-
- }
-
-
- }
-
- }
- return max; // 返回最大子串大小。返回-1则不存在
- }
复制代码 |