[编程题目]给一个String,查找出现多于一次的的substring

[编程题目]给一个String,查找出现多于一次的的substring.
例如:
abcabcaacb >> abc
aababa >> aba

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* find_same_substring(char* pStart, int str_len) {
	printf("search substring %s, len:%u\n",pStart,str_len);
	if(strlen(pStart)<=str_len) {
		return NULL;
	}
	char* pCharIdx = pStart+1;
	while(strlen(pCharIdx)>=str_len) {
		printf("compare %s,%s, len:%u\n",pCharIdx,pStart,str_len);
		if(0 == strncmp(pCharIdx,pStart,str_len)) {
			return pCharIdx;
		}
		++pCharIdx;
	}
	return NULL;
}

char* find_longest_dup_substring(char * str,int len) {
	char* pChar = 0;
	printf("search string %s with length %u",str,len);
	if((NULL == str) || (0 == str[0])) {
		return NULL;
	}
	while(str && (strlen(str)>= len) &&(NULL == (pChar = find_same_substring(str,len)))) {
		++str;
	}
	return pChar;
}
char * find_longest_same_substring_from_start(char* str, int *len) {
	char* pChar = 0;
	if((NULL == str) || (0 == str[0]) || (NULL == len)) {
		return NULL;
	}
	*len = 0;
	printf("find longest same substring %s\n",str);
	int str_len = strlen(str)-1;
	while(str_len>0) {
		if(NULL != (pChar = find_longest_dup_substring(str,str_len))) {
			*len = str_len;
			return pChar;
		}
		str_len--;        
	}
	return NULL;
}


int main(int argc, char* argv[]) 
{
	char* p = 0;
	int len = 0;
	char *result = 0;
	if(argc!=2) {
		printf("Please give one string as parameter\n");
		return 0;
	}
	if(NULL != (p = find_longest_same_substring_from_start(argv[1],&len))) {
		result = (char*)malloc(len+1);
		strncpy(result,p,len);
		result[len]=0;
		printf("find it : %s, len :%u\n",result,len);
		free(result);
	} else {
		printf("no finding\n");
	}
	return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>