#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SetSize 256 //字符集大小
//說明:查找字符串中字符間不同的最大子串
//參數(shù):string 待搜索字符串
// rst 存放找到的最大子串
//返回:找到最大子串長度
int findMaxSubstring(const char *string, char *rst)
{
const char *p = string;
const char *substring = p; //當(dāng)前子串
int length = 0; //當(dāng)前子串長度
const char *maxSubstring = substring; //已經(jīng)找到的最大子串
int maxLength = 0; //已經(jīng)找到的最大子串長度
// 遍歷字符串過程中,字符最后一次出現(xiàn)的位置
const char* position[SetSize];
memset(position, 0, SetSize * sizeof(char *));
char ch; //
while ((ch = *p) != '\0')
{ 
if (position[ch] < substring)
{ //字符在當(dāng)前子串首次出現(xiàn)
length++;
if (length > maxLength)
{
maxSubstring = substring;
maxLength = length;
}
} 
else
{
substring = position[ch] + 1; //當(dāng)前子串從該字符上次出現(xiàn)的位置后面開始
length = p - position[ch];
}
position[ch] = p; // 保存字符的位置
p++;
}
// 拷貝找到的最大子串
strncpy(rst, maxSubstring, maxLength);
rst[maxLength] = '\0';
return maxLength;
} 


據(jù)說這是微軟面試題。


