Chinaunix首页 | 论坛 | 博客
  • 博客访问: 464075
  • 博文数量: 68
  • 博客积分: 2606
  • 博客等级: 上尉
  • 技术积分: 1308
  • 用 户 组: 普通用户
  • 注册时间: 2010-12-13 23:01
文章分类
文章存档

2012年(6)

2011年(62)

分类: C/C++

2011-08-26 16:34:27

------------------------------------------
本文为本人原创,欢迎转载!
转载请注明出处:snowboy.blog.chinaunix.net
雪夜流星
------------------------------------------
1.在字符串中查找最长重复子串:
   写一个函数,找出一个字符串中最长的重复子串。“t1t1”结果就是t1."cabcabca"结果就是cab或者abc或者bca。
说明:
假设str中有长度为m的连续子串,则字符串移动m个位置后,与原串
 s0 s1 s2 s3 ... sm-1 sm sm+1 sm+2 ..... sn
                            s0   s1  s2 .............sn
一定有连续m个位置的字符是相等的;如果有多个解,只返回第一个;
实现代码如下:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define BUF_MAX 1000

  4. int index1; //子串起始位置(数组中的索引)
  5. int len;//子串长度
  6. void str_search(const char *str, char *sub)
  7. {
  8.      int i=0;
  9.     int strlen = 0;
  10.     
  11.     /*计算源字符串的长度*/
  12.     while(str[i]!='\0')
  13.     {
  14.         ++i;
  15.     }
  16.      strlen=i;
  17.     
  18.     /*子串最大可能长度为总字符串长度的一半,如果未找到,依次递减继续查找*/
  19.     for(i=strlen/2;i>0;--i)
  20.     {
  21.         int zeronum=0;//重复字符子串个数计数
  22.         int j;
  23.         int k;
  24.         
  25.         for(j=i;j<strlen;++j)
  26.         {
  27.             /*对源字符串距离为i的字符进行比较,如果相等,计数加1,当连续计数等于i时,
  28.             将子串以及相关参数保存;否则计数清零*/
  29.             if (str[j]==str[j-i])
  30.             {
  31.                 ++zeronum;
  32.                 if (zeronum==i)
  33.                 {
  34.     memcpy(sub, str+j-2i+1, i);
  35.     sub[i] ='\0';
  36.     /*用上面两行代码注释下列代码
  37.                     index1=j-2*i+1;
  38.                     len=i;
  39.                     for(k=0; k<len; k++)
  40.                     {
  41.                         sub[k] = str[index1+k];
  42.                     }
  43.                     sub[len] = '\0';
  44.                     */
  45.                     return;
  46.                 }
  47.             }
  48.             else
  49.             {
  50.                 zeronum=0;
  51.             }
  52.         }
  53.     }
  54. }

  55. int main()
  56. {
  57.      char str[BUF_MAX];
  58.      char sub[BUF_MAX];
  59.     
  60.      scanf("%s",str);
  61.      str_search(str,sub);
  62.     
  63.      printf("%d:%d\n",index1,len);
  64.      printf("sub string:\n");
  65.      printf(sub);
  66.      printf("\n");
  67.     return 0;
  68. }

 

2.在字符串中查找子串并返回子串的位置

实现代码如下:

 

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

  4. char *substr_search(const char *s1, const char *s2, int *postion)
  5. {
  6.     int n = 0;
  7.     int pos = 0;
  8.     
  9.     /*判空*/
  10.     if(*s2)
  11.     {
  12.        /*匹配s2,如果未完全匹配,当s1指针更新到字符串末尾时循环退出*/
  13.         while(*s1)//if(*s1),曾在此处犯下低级错误,希望读者不再重蹈覆辙.
  14.         {        
  15.                 /*匹配子串s2,如果能够连续匹配s2到字符串尾,则保存偏移的位置,返回此位置开始的
  16.                   一段字符串;否则更新计数pos,更新源字符串的值s1*/
  17.                 for(n=0; *(s1+n)==*(s2+n); n++)
  18.                 {
  19.                     if(*(s2+n+1) == '\0')
  20.                     {                            
  21.                         *postion = pos;
  22.                         return (char *)s1;
  23.                     }
  24.                 }
  25.                 
  26.                 pos++;
  27.                 s1++;
  28.         }
  29.         
  30.         printf("couldn't been found the sub string\n");
  31.         *postion = 0;//当不能找到子串时,将传出参数赋值为0
  32.         return NULL;
  33.     }
  34.     else
  35.     {
  36.         printf("the s2 string is NULL\n");
  37.         *postion = pos;
  38.         return (char *)s1;
  39.     }
  40. }

  41. int main(void)
  42. {
  43.     char str1[100] = "abcdefghijkl";
  44.     char str2[100] = "fgh";
  45.     char *tmp = NULL;
  46.     int pos;
  47.     
  48.     printf("str1:%s",str1);
  49.     printf("\n");
  50.     printf("str2:%s",str2);
  51.     printf("\n");
  52.     
  53.     tmp = substr_search(str1, str2, &pos);        
  54.     printf("the sub string postion:%d\n", pos);    
  55.     printf("return string:");
  56.     printf("%s\n",tmp);
  57.     
  58.     return 0;
  59. }
阅读(1979) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~