首页 > 代码库 > 找出一个字符串中最长重复次数的子字符串,并计算其重复次数
找出一个字符串中最长重复次数的子字符串,并计算其重复次数
原题
找出一个字符串中最长重复次数的子字符串,并计算其重复次数。例如:字符串“abc fghi bc kl abcd lkm abcdefg”,并返回“abcd”和2。
我的思路
为了方便表述,我们使用变量src作为原字符串,sub_str作为子字符串。
由于题目要求寻找至少重复2次的最长的子字符串,重点在于最长的子字符串,而不在于重复的最多次数。因此我们可以从长度最长的字符串入手,计算其重复次数。只要重复达到2次,即可返回该字符串。
显然长度最长的子字符串就是原串本身,其重复次数为1,不符合要求。因此我们的外层循环可以从len = strlen(src)开始,直到len = 1为止,其中只要重复次数达到2次,即返回该字符串,若均没有重复,则返回0。
为了主函数比较清晰,我将整个程序拆分为3部分,如下
int find_longest_dup_str(char* src, char* dest);int str_sub(char* src, char* sub, int pos,int len);int str_cnt(char* src,char* sub);
其中find_longest_dup_str实现的功能即为将重复次数2次及2次以上的最长字符串存入dest中,并返回其重复次数。
str_sub实现的功能是将原串src中,从位置pos开始,长度为len的子字符串,存入sub中。
str_cnt则是计算了sub子串重复的次数
实现代码
/************************************************************************* > File Name: testmain.c > Author: KrisChou > Mail:zhoujx0219@163.com > Created Time: Sun 17 Aug 2014 02:56:28 PM CST ************************************************************************/#include <stdio.h>#include <stdlib.h>#include <string.h>int find_longest_dup_str(char* src, char* dest);int str_sub(char* src, char* sub, int pos,int len);int str_cnt(char* src,char* sub);int main(int argc, char* argv[]){ char str[] = "abc fghi bc kl abcd lkm abcdefg"; char sub[128] = ""; int cnt; cnt = find_longest_dup_str(str,sub); printf("result: %s\ncnt: %d \n",sub,cnt);}int find_longest_dup_str(char* src, char* dest){ int len; int index; int cnt; for(len = strlen(src);len > 0;len--) { for(index = 0; index + len-1 < strlen(src); index++) { str_sub(src,dest,index,len); if((cnt = str_cnt(src,dest)) >= 2) { return cnt; } } } return 0;}int str_sub(char* src, char* sub, int pos,int len){ int index; for(index = 0; index < len;index++) { sub[index] = src[pos + index]; } sub[index] = ‘\0‘;}int str_cnt(char* src,char* sub){ int cnt = 0; char tmp[128]; int index; int index_sub; for(index = 0;index + strlen(sub)-1 < strlen(src);index++) { /* method1 for(index_sub = 0; index_sub < strlen(sub);index_sub++) { if(src[index + index_sub] != sub[index_sub]) { break; } } if(index_sub == strlen(sub)) { cnt++; } */ /* method2 str_sub(src,tmp,index,strlen(sub)); if(strcmp(sub,tmp) == 0) { cnt++; } */ // method3 if(strncmp(src + index,sub,strlen(sub))== 0) { cnt++; } } return cnt;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。