[搜狗] 找一个字符串中包含全部出现字符的最小字符串

一个字符串中含有n个字符，其中有m个不同的字符，n>>m，用最少的时间和空间找到包含所有这m个字符的最短的字串，不考虑特殊字符，只考虑字母数字即可。

例如：

abccbaddac,返回：cbad

aabcadbbbcca，返回：bcad

实现代码：

#include <iostream>
using namespace std;
void Search(char input[], char output[]);
int main()
{
	char* input = "abccbaddac";
	char* output = new char[strlen(input)];
	Search(input,output);
	cout<<output<<endl;
}

void Search(char input[], char output[])
{
	bool num[10] = {0}; //数字字符
	bool small[26] = {0}; //小写字符
	bool big[26] = {0}; //大写字符
	int sum = 0; //不同字符的个数
	int temp, index;
	for (int i = 0; i < strlen(input); i++)
	{
		temp = input[i];
		if (temp >= 97)
		{
			index = input[i] - 'a';
			if (small[index] == 0)
			{
				small[index] = 1;
				sum++;
			}
		}
		else if (temp <= 57)
		{
			index = input[i] - '0';
			if (num[index] == 0)
			{
				num[index] = 1;
				sum++;
			}
		}
		else
		{
			index = input[i] - 'A';
			if (big[index] == 0)
			{
				big[index] = 1;
				sum++;
			}
		}
	}

	bool t_num[10] = {0}; //数字字符
	bool t_small[26] = {0}; //小写字符
	bool t_big[26] = {0}; //大写字符
	int t_sum = 0;

	int min = strlen(input);
	char* out = new char[strlen(output) + 1];
	memset(out,0,sizeof(out));

	for (int i = 0; i < strlen(input); i++)
	{
		char* pout = out;
		t_sum = 0;
		memset(t_num,0,sizeof(t_num));
		memset(t_small,0,sizeof(t_small));
		memset(t_big,0,sizeof(t_big));
		int j = i;
		while(j < strlen(input))
		{
			*pout++ = input[j];
			temp = input[j];
			if (temp >= 97)
			{
				index = input[j] - 'a';
				if (t_small[index] == 0)
				{
					t_small[index] = 1;
					t_sum++;
				}
			}
			else if (temp <= 57)
			{
				index = input[j] - '0';
				if (t_num[index] == 0)
				{
					t_num[index] = 1;
					t_sum++;
				}
			}
			else
			{
				index = input[j] - 'A';
				if (t_big[index] == 0)
				{
					t_big[index] = 1;
					t_sum++;
				}
			}
			if (t_sum == sum)
			{
				int len = j - i;
				if(min > len)
				{
					min = len;
					*pout = '\0';
					strcpy(output,out);
					j = i + len - sum;
					break;
				}
			}
			j++;
		}
	}
	delete [] out;
}

转自：http://blog.csdn.net/foreverling/article/details/43486515