Use a std::unordered_map<char, size_t>
to store the indices past the last occurance of a certain char.
Keep the currently best match as well as the match you currently test. Iterating through the chars of the input result in 2 cases you need to handle:
- the char already occured and the last occurance of the char requires you to move the start of the potential match to avoid the char from occuring twice: Update the answer with the match ending just before the current char, if that's better than the current answer.
- Otherwise: Just update the map
void printsubstring(const char* input)
{
std::unordered_map<char, size_t> lastOccurances;
Answer answer{ 0, 0 };
size_t currentPos = 0;
size_t currentStringStart = 0;
char c;
while ((c = input[currentPos]) != 0)
{
auto entry = lastOccurances.insert({ c, currentPos + 1 });
if (!entry.second)
{
if (currentStringStart < entry.first->second && currentPos - currentStringStart > answer.length)
{
// need to move the start of the potential answer
// -> check, if the match up to the char before the current char was better
answer.start = currentStringStart;
answer.length = currentPos - currentStringStart;
currentStringStart = entry.first->second;
}
entry.first->second = currentPos + 1;
}
++currentPos;
}
// check the match ending at the end of the string
if (currentPos - currentStringStart > answer.length)
{
answer.start = currentStringStart;
answer.length = currentPos - currentStringStart;
}
std::cout << answer.start << ", " << answer.length << std::endl;
std::cout << std::string_view(input + answer.start, answer.length) << std::endl;
}
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…