Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1902817
  • 博文数量: 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-08-16 15:59:09

在数据结构的书上有这个问题的描述。

问题描述:已知一字符串str,并给出字串sub_str,然后判断sub_str是不是在str中,并且输出相应的信息。

算法描述:使用三个指示器——i, j, start。

start:表示每趟比较的时候str的起点。

i:表示在每趟比较当中,str的移动指针。

j:表示在每趟比较当中,sub_str的移动指针。

  1. #include <stdio.h>
  2. #include <string.h>

  3. #define M 20

  4. int main()
  5. {
  6.     char str[M], sub_str[M];
  7.     int i, j, start;

  8.     fprintf(stdout, "Input string:\n");
  9.     fscanf(stdin, "%s", str);
  10.     fprintf(stdout, "Input sub string:\n");
  11.     fscanf(stdin, "%s", sub_str);
  12.     
  13.     start = 0;
  14.     i = start;
  15.     j = 0;
  16.     while(i < strlen(str) && j < strlen(sub_str)) {
  17.         if(str[i] == sub_str[j]) {
  18.             i++;
  19.             j++;
  20.         } else {
  21.             start++;
  22.             i = start;
  23.             j = 0;
  24.         }
  25.     }
  26.     
  27.     if(j == strlen(sub_str)) {
  28.         printf("match successfully~\n");
  29.     } else {
  30.         printf("match unsuccessfully~\n");
  31.     }

  32.     return 0;
  33. }

测试结果:

  1. ^_^[sunny@sunny-laptop ~/DS]102$ ./a.out
  2. Input string:
  3. abcdefg
  4. Input sub string:
  5. abc
  6. match successfully~
  7. ^_^[sunny@sunny-laptop ~/DS]103$ ./a.out
  8. Input string:
  9. abcdefg
  10. Input sub string:
  11. hi[]
  12. match unsuccessfully~

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

sunjiangang-ok2011-08-28 07:56:55

zhanglistar: 博主这个不是很高效的。首先start变量是不需要的。
其次,失配时 应该让  i 滑的更远。
改为: i = i - j + 1;.....
哦,zhanglistar说得对,谢谢~

zhanglistar2011-08-27 22:56:38

博主这个不是很高效的。首先start变量是不需要的。
其次,失配时 应该让  i 滑的更远。
改为: i = i - j + 1;