Task:

A string is given, no longer than 200,000 characters. It is necessary to print all the substrings (a successive sequence of characters within this string) using the set.

My solution logic is:

#include <iostream> #include <set> #include <cstring> #include <iterator> using namespace std; int main () { char s[200001] = {}; set <char*> mySet; cin >> s; int len = strlen(s); for (int i = 0; i < len; ++i) for (int j = 1; j <= len - i; ++j) { char s1[200001] = {}; strncpy(s1, s + i, j); mySet.insert(s1); } copy(mySet.begin(), mySet.end(), ostream_iterator<char*>(cout, " ")); return 0; }

Problem:

Only 1 element is entered into the set (seemingly only the first substring, i.e. 'a')

Enter:

abba

Conclusion:

a

Should output:

a ab abb abba b bb bba ba

  • OK, and the question is what? Fix a drop, will it fit in time / memory? - KoVadim 2:13 pm
  • 200000 and squared ... can you imagine the amount of memory? 40 gigabytes or was I wrong? - pavel
  • I don’t understand what the problem is, why only one element is entered into the set - Dmitry Nishchev

2 answers 2

It is logical that nothing "does not work." You do not have a lot of lines (as it seems at first glance), but pointers. And always there is only one and the same pointer s1. The fact that different lines are copied there every time - well, it happens. The pointer itself does not change. Therefore, in a set is always either zero or one pointer. What is the last line left - that will be.

"easy rewriting" to more c ++ code immediately solves all spaces

 #include <iostream> #include <set> #include <cstring> #include <iterator> using namespace std; int main () { string s; set <string> mySet; cin >> s; int len = s.length(); for (int i = 0; i < len; ++i) for (int j = 1; j <= len - i; ++j) { string s1 = s.substr(i,j); mySet.insert(s1); } for (auto x:mySet) { cout << x << " ";} cout << endl; return 0; }

    You allocate huge arrays on the stack - this is not good. But the main thing is that you save a pointer to the array on the stack array mySet.insert(s1) . After each iteration, the pointer becomes invalid because the array on the stack goes out of scope and you get undefined behavior. I would venture to suggest that at each subsequent iteration the added pointer will point to the same stack area and new data is simply not added.

    Use std::string instead of raw arrays. Or let's say std::string together with string_view .