posts - 3,  comments - 6,  trackbacks - 0
#include <stdio.h>
#include 
<stdlib.h>
#include 
<string.h>

#define SetSize 256 //字符集大小

//说明:查找字符串中字符间不同的最大子串
//参数:string 待搜索字符串
//        rst 存放找到的最大子串
//返回:找到最大子串长度
int findMaxSubstring(const char *stringchar *rst){

    
const char *= 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 阅读(471) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理