趋势科技一道编程题

题目：编写一个函数int search(char *text)，text为输入的字符串，从字符串中找出一个最长的
不含重复字符的子字符串，例如“axdbx”,返回4，子字符串为“axdb”，而“axdbxce”,返回5，子字
符串为“dbxce”。
 
 
 
[cpp]  
#include<iostream>  
#include<string>  
  
using namespace std;  
  
int search(char *text)  
{  
    int pos[256];                   //映射到每一个字符，记录这个字符最近出现的位置  
    int i,start,end,max,curlength;  
    int curstart = 0;  
    start = 0;                     //最长字符起始位置  
    end = strlen(text);  
    curlength = max = 0;  
  
    for(i=0;i<256;i++)              //辅助数组的初始化  
        pos[i] = -1;  
  
    for(i=1;i<end;i++)  
    {  
        int index = text[i];  
        if(pos[index]>=start)            //如果此字符出现过  
        {  
            curlength = i - start;      //得到这段字符串的长度  
            if(curlength>max)  
            {  
                start = curstart;  
                max=curlength;  
            }  
            curstart = pos[index]+1;   //新的字符串从下一个位置开始  
        }  
        pos[index] = i;             //记录此字符最近出现位置  
    }  
  
    curlength = end - curstart;     //最后处理  
    if(curlength > start)  
    {  
        max = curlength;  
        start = curstart;               //最后start保存的最长的子字符串的起始位置  
    }  
    return max;  
}  
  
int main(void)  
{  
    char *str="axdbxce";  
    cout<<search(str)<<endl;  
    return 0;  
}  
 

补充：软件开发 , C++ ,

上一个：算法学习笔记----归并排序
下一个：九度1048 判断三角形类型