查找字符串中字符间不同的最大子串

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define SetSize 256 //字符集大小

//说明：查找字符串中字符间不同的最大子串

//参数：string 待搜索字符串

// rst 存放找到的最大子串

//返回：找到最大子串长度

int findMaxSubstring(const char *string, char *rst){

const char *p = string;

const char *substring = p; //当前子串

int length = 0; //当前子串长度

const char *maxSubstring = substring; //已经找到的最大子串

int maxLength = 0; //已经找到的最大子串长度

// 遍历字符串过程中，字符最后一次出现的位置

const char* position[SetSize];

memset(position, 0, SetSize * sizeof(char *));

char ch; //

while ((ch = *p) != '\0')

{

if (position[ch] < substring){ //字符在当前子串首次出现

length++;

if (length > maxLength){

maxSubstring = substring;

maxLength = length;

}

else {

substring = position[ch] + 1; //当前子串从该字符上次出现的位置后面开始

length = p - position[ch];

}

position[ch] = p; // 保存字符的位置

p++;

}

// 拷贝找到的最大子串

strncpy(rst, maxSubstring, maxLength);

rst[maxLength] = '\0';

return maxLength;

}

据说这是微软面试题。

posted on 2010-08-29 17:30 custa 阅读(607) 评论(0) 编辑收藏引用

常用链接

留言簿

随笔档案

My Blogs

搜索

最新评论

阅读排行榜

评论排行榜

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理