一道题:给一个字符串,和一个字符集,求该字符串包含所有字符集的最短子串

2016-12-14 09:54:43来源:http://blog.csdn.net/cwqbuptcwqbupt/article/details/7467388作者:cwqbuptcwqbupt人点击

第七城市
比如字符集“abc”.个数为M。
字符串:“xxxbxxaxbxxbaxxaaxxcxx”
可知要求的最短子串是:baxxaaxxc。仔细分析最短串发现:
1。b与c在最短串中仅出现一次,正好是一头一尾。
2。中间的字符a,在最短串中可能出现了多次,但对于a而言如果只看它最后一次出现在最短串中,则之前不管是否出现过的都是无所谓的,比如最短串部分改成“bxxxxaxxc”,并不影响结果。
综合考虑上述两点,决定最短串长度的,只是字符集里的所有字符在最短串中最后一次出现的索引。为此,可设一个长为字符集个数M的数组,当遍历字符串时,不停的更新各字符
集最后出现的索引。同时,每字符集里的字符出现时,就要根据现有记录的索引去判断是否有最短子串产生。
时间复杂度:每次遍历遇到字符集出现,做一个判断O(M),因此总复杂度为O(N*M)。


#include 
#include
#define N 100
#define M 3
char str[N] = "xbxaxaxbxaxcxcaxbxxaxbxcxxaxbcxaxcbcc";//母串
char ch[M] = "abc";//字符集
/*
函数功能:测试字符c是否在字符集中,若在,返回该字符在字符集中的索引
*/
int is_exit(char c)
{
int i=0;
for(i=0;i {
if( c == ch[i] )
return i;
}
return -1;
}
/*
函数功能:根据目前记录的各字符集索引,算出最短子串长,子串的起始索引
*/
void dis(int* mindis_idx,int *pdis,int* start_idx)
{
int min_idx = 0;
int min_val = mindis_idx[0];
int max_idx = 0;
int max_val = mindis_idx[0];
int i=1;
for(;i {
if( mindis_idx[i] == -1 )
return;
if( mindis_idx[i] < min_val )
{
min_val = mindis_idx[i];
min_idx = i;
}
if( mindis_idx[i] > max_val )
{
max_val = mindis_idx[i];
max_idx = i;
}
}
*pdis = max_val - min_val +1;
*start_idx = min_val;
}
void show_substr(int start_idx,int d)
{
char * ss = (char*)malloc(d+1);
ss[d]=0;
if(ss)
{
memcpy(ss,str+start_idx,d);
printf("The substring=%s/n",ss);
}
free(ss);
}
void main()
{
int mindis_idx[M];//记录当前字符集里每个字符在母串中的“当前”最大索引,这里的“当前”是指遍历索引的当前值
memset(mindis_idx,-1,M*sizeof(int)); //初始化为-1,这非常关键,当计算最短距时,若遇到有-1,证明目前还没收集满所有字符集
int d = N;//最短子串长
int start_idx = 0;//当前最短子串的起始索引
int i=0;
for(;i {
int r=0;
if( (r=is_exit(str[i]))!=-1 )//找到一个在字符集中的元素
mindis_idx[r] = i;

int temp_d = d;
int temp_start_idx = start_idx;
dis(mindis_idx,&temp_d,&temp_start_idx);//测试当前索引i的最短子串
if( temp_d < d )
{
d = temp_d;
start_idx = temp_start_idx;
}
}
printf("The min dis=%d/n",d);
show_substr(start_idx,d);
}



第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台