4
糖果
分析：利用标记数组visit[256]来保存出现过的字符，然后从头开始遍历字符串。
1、如果当前字符str[i]没有出现过，则将visit[str[i]]标记为1，表示已经出现过，同时将字串的长度len加1。
2、如果当前字符str[i]已经出现过，即visit[str[i]]==1，则表示一个局部最长不重复子串已经出现。此时判断该子串长度len是否大于mlen，如果是，则更新mlen，以及最长子串的起始位置mstart。同时将start到重复字符str[i]之间的visit数组重置为0，相应的长度len也减小，然后从str[i]的下个字符作为新的子串的开始。代码如下：
#include <iostream>
#include <cstring>
using namespace std;
int visit[256],start=0,mstart=0,mlen=0,i=0,len=0;
int main(){
string str;
cin>>str;
while(i!=str.size()){
if(visit[str[i]]==1){
if(len>mlen){
mstart=start;
mlen=len;
}
while(str[start]!=str[i]){
visit[str[start]]=0;
start++;
len–;
}
start++;
}
else{
visit[str[i]]=1;
len++;
}
i++;
}
if(len>mlen){
mlen=len;
mstart=start;
}
if(mlen == str.size()){
cout <<-1<< endl;
}else{
cout << mlen << endl;
}
return 0;
}
转自公众号：
noip案例讲解