题目:编写一个函数int search(char *text),text为输入的字符串,从字符串中找出一个最长的
不含重复字符的子字符串,例如“axdbx”,返回4,子字符串为“axdb”,而“axdbxce”,返回5,子字
符串为“dbxce”。
#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; }