Longest substrings without repeating characters: Difference between revisions
Longest substrings without repeating characters (view source)
Revision as of 11:08, 4 June 2021
, 3 years agoAdded C++ solution
(Added C++ solution) |
|||
Line 8:
<br><br>
=={{header|C++}}==
<lang cpp>#include <iostream>
#include <fstream>
#include <set>
#include <sstream>
#include <string>
#include <vector>
std::vector<std::string> longest_substrings_without_repeats(const std::string& str) {
size_t max_length = 0;
std::vector<size_t> offsets;
size_t length = str.size();
for (size_t offset = 0; offset < length; ++offset) {
std::set<char> characters;
size_t len = 0;
for (; offset + len < length; ++len) {
if (characters.find(str[offset + len]) != characters.end())
break;
characters.insert(str[offset + len]);
}
if (len > max_length) {
offsets.clear();
max_length = len;
}
if (len == max_length)
offsets.push_back(offset);
}
std::vector<std::string> result;
for (size_t offset : offsets)
result.push_back(str.substr(offset, max_length));
return result;
}
void print_strings(const std::vector<std::string>& strings) {
std::cout << "[";
for (size_t i = 0, n = strings.size(); i < n; ++i) {
if (i > 0)
std::cout << ", ";
std::cout << '\'' << strings[i] << '\'';
}
std::cout << "]";
}
void test1() {
for (std::string str : { "xyzyabcybdfd", "xyzyab", "zzzzz", "a", "thisisastringtest", "" }) {
std::cout << "Input: '" << str << "'\nResult: ";
print_strings(longest_substrings_without_repeats(str));
std::cout << "\n\n";
}
}
std::string slurp(std::istream& in) {
std::ostringstream out;
out << in.rdbuf();
return out.str();
}
void test2(const std::string& filename) {
std::ifstream in(filename);
if (!in) {
std::cerr << "Cannot open file '" << filename << "'.\n";
return;
}
std::cout << "Longest substring with no repeats found in '" << filename << "': ";
print_strings(longest_substrings_without_repeats(slurp(in)));
std::cout << "\n";
}
int main() {
test1();
test2("unixdict.txt");
}</lang>
{{out}}
<pre>
Input: 'xyzyabcybdfd'
Result: ['zyabc', 'cybdf']
Input: 'xyzyab'
Result: ['zyab']
Input: 'zzzzz'
Result: ['z', 'z', 'z', 'z', 'z']
Input: 'a'
Result: ['a']
Input: 'thisisastringtest'
Result: ['astring', 'ringtes']
Input: ''
Result: []
Longest substring with no repeats found in 'unixdict.txt': ['mbowel
disgrunt']
</pre>
=={{header|Julia}}==
| |||