壹串首尾相連的珠子(m?個)，有?N?種顏色(N<=10)，
設計壹個算法，取出其中壹段，要求包含所有?N?中顏色，並使長度最短。
*/
#include?<stdio.h>
#include?<stdlib.h>
#include?<string.h>
int?shortestlengh(char?*?in,?char?**?dst,?int?N)
{
//變成inin的形式，避免求余
int?nlen?=?strlen(in);
char?*?in2?=?(char?*)malloc(2?*?nlen?*?sizeof(char));?
memcpy(in2,?in,?nlen?*?sizeof(char));
memcpy(in2?+?nlen,?in,?nlen?*?sizeof(char));
int?start?=?0,?end?=?nlen?-?1;
int?shortestlen?=?nlen;
int?hash[256]?=?{0};
int?colornum?=?0;
int?s?=?0,?e?=?-1;
//遍歷所有可能的起始點
while(s?<?nlen)
{
while(colornum?<?N?&&?e?<=?2?*?nlen)?//找到在當前起點下找到所有顏色的結尾
{
e++;
if(hash[int(in2[e])]?==?0)
{
colornum++;
}
hash[int(in2[e])]++;
}
//去掉前面相同的部分
while(in2[s]?==?in2[s?+?1])
{
s++;
hash[(int)in2[s]]--;
}
//更新最短的串
if(shortestlen?>?e?-?s?+?1)
{
shortestlen?=?e?-?s?+?1;
start?=?s;
end?=?e;
}
//更新s,從下壹個顏色開始
hash[(int)in2[s]]--;
if(hash[(int)in2[s]]?==?0)
{
colornum--;
}
s?=?s?+?1;
}
*(dst)?=?(char?*)malloc(end?-?start?+?2);
memcpy(*dst,?in2?+?start,?end?-?start?+?1);
(*dst)[end?-?start?+?1]?=?'\0';?//註意
free(in2);
return?end?-?start?+?1;
}
int?main()
{
char?*?s?=?"addcddcbccbba";
char?*?d?=?NULL;
int?n?=?shortestlengh(s,?&d,?4);
printf("%d\n%s\n",?n,?d);
return?0;
}