------------------------------------------
本文为本人原创,欢迎转载!
雪夜流星
------------------------------------------
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个位置的字符是相等的;如果有多个解,只返回第一个;
实现代码如下:
- #include <stdio.h>
- #include <stdlib.h>
- #define BUF_MAX 1000
- int index1; //子串起始位置(数组中的索引)
- int len;//子串长度
- void str_search(const char *str, char *sub)
- {
- int i=0;
- int strlen = 0;
-
- /*计算源字符串的长度*/
- while(str[i]!='\0')
- {
- ++i;
- }
- strlen=i;
-
- /*子串最大可能长度为总字符串长度的一半,如果未找到,依次递减继续查找*/
- for(i=strlen/2;i>0;--i)
- {
- int zeronum=0;//重复字符子串个数计数
- int j;
- int k;
-
- for(j=i;j<strlen;++j)
- {
- /*对源字符串距离为i的字符进行比较,如果相等,计数加1,当连续计数等于i时,
- 将子串以及相关参数保存;否则计数清零*/
- if (str[j]==str[j-i])
- {
- ++zeronum;
- if (zeronum==i)
- {
- memcpy(sub, str+j-2i+1, i);
- sub[i] ='\0';
- /*用上面两行代码注释下列代码
- index1=j-2*i+1;
- len=i;
- for(k=0; k<len; k++)
- {
- sub[k] = str[index1+k];
- }
- sub[len] = '\0';
- */
- return;
- }
- }
- else
- {
- zeronum=0;
- }
- }
- }
- }
- int main()
- {
- char str[BUF_MAX];
- char sub[BUF_MAX];
-
- scanf("%s",str);
- str_search(str,sub);
-
- printf("%d:%d\n",index1,len);
- printf("sub string:\n");
- printf(sub);
- printf("\n");
- return 0;
- }
2.在字符串中查找子串并返回子串的位置
实现代码如下:
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- char *substr_search(const char *s1, const char *s2, int *postion)
- {
- int n = 0;
- int pos = 0;
-
- /*判空*/
- if(*s2)
- {
- /*匹配s2,如果未完全匹配,当s1指针更新到字符串末尾时循环退出*/
- while(*s1)//if(*s1),曾在此处犯下低级错误,希望读者不再重蹈覆辙.
- {
- /*匹配子串s2,如果能够连续匹配s2到字符串尾,则保存偏移的位置,返回此位置开始的
- 一段字符串;否则更新计数pos,更新源字符串的值s1*/
- for(n=0; *(s1+n)==*(s2+n); n++)
- {
- if(*(s2+n+1) == '\0')
- {
- *postion = pos;
- return (char *)s1;
- }
- }
-
- pos++;
- s1++;
- }
-
- printf("couldn't been found the sub string\n");
- *postion = 0;//当不能找到子串时,将传出参数赋值为0
- return NULL;
- }
- else
- {
- printf("the s2 string is NULL\n");
- *postion = pos;
- return (char *)s1;
- }
- }
- int main(void)
- {
- char str1[100] = "abcdefghijkl";
- char str2[100] = "fgh";
- char *tmp = NULL;
- int pos;
-
- printf("str1:%s",str1);
- printf("\n");
- printf("str2:%s",str2);
- printf("\n");
-
- tmp = substr_search(str1, str2, &pos);
- printf("the sub string postion:%d\n", pos);
- printf("return string:");
- printf("%s\n",tmp);
-
- return 0;
- }
阅读(1975) | 评论(0) | 转发(1) |