Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1869573
  • 博文数量: 217
  • 博客积分: 4362
  • 博客等级: 上校
  • 技术积分: 4180
  • 用 户 组: 普通用户
  • 注册时间: 2009-09-20 09:31
文章分类

全部博文(217)

文章存档

2017年(1)

2015年(2)

2014年(2)

2013年(6)

2012年(42)

2011年(119)

2010年(28)

2009年(17)

分类: C/C++

2011-09-19 08:15:00

问题描述:输入两个字符串,求得两个字符串的最大字串。
问题分析:为了求得两个字符串的最大字串,其中一种思路是这样的。两个字符窗分别为a和b    (strlen(a)<=strlen(b)),取长度较小的那个字串b,假如它的长度为n,第一次用长度为n的子串进行与a匹配,如果没有匹配成功,用n-1长度的所有子串与a进行匹配,如果没有匹配成功,继续用长度减小的下一个所有子串进行匹配,直到匹配成功。
程序实现:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. char *max_str(char *long_str, char *short_str)
  5. {
  6.     char *tmp = NULL;
  7.     int i, j;

  8.     tmp = malloc(256);
  9.     for(i = strlen(short_str); i > 0; i--) {
  10.         for(j = strlen(short_str)-1; j >= i-1; j--) {
  11.             memcpy(tmp, &short_str[j-i+1], i);
  12.             tmp[i] = 0;
  13.             if(strstr(long_str, tmp) != NULL) {
  14.                 return tmp;
  15.             }
  16.         }
  17.     }
  18.     return NULL;
  19. }

  20. int main()
  21. {
  22.     char *str1 = malloc(256);
  23.     char *str2 = malloc(256);
  24.     char *res = NULL;

  25.     scanf("%s %s", str1, str2);
  26.     if(strlen(str1) > strlen(str2)) {
  27.         res = max_str(str1, str2);
  28.     } else {
  29.         res = max_str(str2, str1);
  30.     }
  31.     printf("str1:%s\n", str1);
  32.     printf("str2:%s\n", str2);
  33.     printf("max sub string:%s\n", res);

  34.     free(str1);
  35.     free(str2);
  36.     free(res);
  37.     return 0;
  38. }
测试结果:
  1. ^_^[sunny@sunny-laptop ~/DS]16$ ./a.out
  2. opencv\@bs][dasf
  3. \@
  4. str1:opencv\@bs][dasf
  5. str2:\@
  6. max sub string:\@
  7. ^_^[sunny@sunny-laptop ~/DS]17$ ./a.out
  8. hello
  9. hello
  10. str1:hello
  11. str2:hello
  12. max sub string:hello
  13. ^_^[sunny@sunny-laptop ~/DS]18$ ./a.out
  14. hello
  15. he
  16. str1:hello
  17. str2:he
  18. max sub string:he
  19. ^_^[sunny@sunny-laptop ~/DS]19$
程序说明:在主函数中得到两个字符串,并且调用max_str()函数进行匹配。其中的char * strstr(char *a, char * b)函数是string.h中的一个函数,该函数的作用是定位字串,如果b在a中出现的话,就返回b,否则返回NULL。




阅读(2046) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~