diff options
| -rw-r--r-- | .settings/language.settings.xml | 4 | ||||
| -rw-r--r-- | Sources/DataStructure.cpp | 289 |
2 files changed, 196 insertions, 97 deletions
diff --git a/.settings/language.settings.xml b/.settings/language.settings.xml index 4e9d73d..e532fea 100644 --- a/.settings/language.settings.xml +++ b/.settings/language.settings.xml @@ -5,7 +5,7 @@ <provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/> <provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/> <provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/> - <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939090329124603581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> + <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-938732924838427581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> <language-scope id="org.eclipse.cdt.core.gcc"/> <language-scope id="org.eclipse.cdt.core.g++"/> </provider> @@ -16,7 +16,7 @@ <provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/> <provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/> <provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/> - <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939090329124603581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> + <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-938732924838427581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> <language-scope id="org.eclipse.cdt.core.gcc"/> <language-scope id="org.eclipse.cdt.core.g++"/> </provider> diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp index 5cfb53c..4c0379b 100644 --- a/Sources/DataStructure.cpp +++ b/Sources/DataStructure.cpp @@ -1,117 +1,216 @@ #include <iostream> -#include <string> #include <vector> +#include <algorithm> +#include <stack> +#include <queue> +#include <unordered_set> //#include <gtest/gtest.h> +//#if defined(__unix__) || defined(__APPLE__) +//#include <sys/resource.h> +//#endif -using std::string; -typedef unsigned long long ull; +using std::vector; +using std::ios_base; +using std::cin; +using std::cout; -struct Data { - string pattern, text; -}; - -Data read_input() { - Data data; - std::cin >> data.pattern >> data.text; - return data; -} - -void print_occurrences(const std::vector<int>& output) { - for (size_t i = 0; i < output.size(); ++i) - std::cout << output[i] << " "; - std::cout << "\n"; -} - -std::vector<int> get_occurrences(const Data& input) { - const string& s = input.pattern, t = input.text; - std::vector<int> ans; - for (size_t i = 0; i + s.size() <= t.size(); ++i) - if (t.substr(i, s.size()) == s) - ans.push_back(i); - return ans; -} +class TreeOrders { +public: + int n; + vector<int> key; + vector<int> left; + vector<int> right; -ull poly_hash(string& S, int p, int x) { - ull hash = 0; + void read() { + cin >> n; + key.resize(n); + left.resize(n); + right.resize(n); + for (int i = 0; i < n; i++) { + cin >> key[i] >> left[i] >> right[i]; + } + } - for (int i = S.size() - 1; i >= 0; --i) - hash = (hash * x + S[i]) % p; - return hash; -} + vector<int> in_order() { + std::stack<int> keyIndexStack; + vector<int> result; + bool walkLeft = true; + int currentIndex = 0; + keyIndexStack.push(currentIndex); + while (!keyIndexStack.empty() || right[currentIndex] != -1) { + if (walkLeft) { + if (left[currentIndex] != -1) { + currentIndex = left[currentIndex]; + keyIndexStack.push(currentIndex); + } else { + result.push_back(key[keyIndexStack.top()]); + keyIndexStack.pop(); + walkLeft = false; + } + } else { + if (right[currentIndex] != -1) { + currentIndex = right[currentIndex]; + keyIndexStack.push(currentIndex); + walkLeft = true; + } else { + if (!keyIndexStack.empty()) { + currentIndex = keyIndexStack.top(); + keyIndexStack.pop(); + result.push_back(key[currentIndex]); + } + } + } + } + return result; + } -std::vector<ull> pre_compute_hashes(string& T, int pattenLength, int p, int x) { - std::vector<ull> H(T.size() - pattenLength + 1); - string S = T.substr(T.size() - pattenLength); - H[T.size() - pattenLength] = poly_hash(S, p, x); - ull y = 1; - for (int i = 0; i < pattenLength; i++) { - y = (y * x) % p; + vector<int> pre_order() { + vector<int> result; + std::stack<int> keyIndexStack; + std::queue<int> keyIndexQueue; + bool walkLeft = true; + int currentIndex = 0; + keyIndexStack.push(currentIndex); + keyIndexQueue.push(currentIndex); + while (!keyIndexStack.empty() || right[currentIndex] != -1) { + if (walkLeft) { + if (left[currentIndex] != -1) { + currentIndex = left[currentIndex]; + keyIndexQueue.push(currentIndex); + keyIndexStack.push(currentIndex); + } else { + keyIndexStack.pop(); + walkLeft = false; + result.push_back(key[keyIndexQueue.front()]); + keyIndexQueue.pop(); + } + } else { + if (right[currentIndex] != -1) { + currentIndex = right[currentIndex]; + keyIndexQueue.push(currentIndex); + keyIndexStack.push(currentIndex); + walkLeft = true; + } else { + if (!keyIndexStack.empty()) { + currentIndex = keyIndexStack.top(); + keyIndexStack.pop(); + result.push_back(key[keyIndexQueue.front()]); + keyIndexQueue.pop(); + } + } + } + } + return result; } - for (int i = T.size() - pattenLength - 1; i >= 0; --i) { - H[i] = (x * H[i + 1] + T[i] - y * T[i + pattenLength]) % p; + + vector<int> post_order() { + vector<int> result; + std::stack<int> keyIndexStack; + std::unordered_set<int> peekedSet; + bool walkLeft = true; + int currentIndex = 0; + keyIndexStack.push(currentIndex); + while (!keyIndexStack.empty()) { + auto search = peekedSet.find(currentIndex); + if (search != peekedSet.end()) { + result.push_back(key[currentIndex]); + peekedSet.erase(currentIndex); + keyIndexStack.pop(); + if (keyIndexStack.empty()) + break; + currentIndex = keyIndexStack.top(); + continue; + } + if (walkLeft) { + if (left[currentIndex] != -1) { + currentIndex = left[currentIndex]; + keyIndexStack.push(currentIndex); + } else { + if (right[currentIndex] == -1) { + result.push_back(key[currentIndex]); + walkLeft = false; + keyIndexStack.pop(); + currentIndex = keyIndexStack.top(); + } else { + peekedSet.insert(currentIndex); + currentIndex = right[currentIndex]; + keyIndexStack.push(currentIndex); + } + } + } else { + if (right[currentIndex] != -1) { + peekedSet.insert(currentIndex); + currentIndex = right[currentIndex]; + keyIndexStack.push(currentIndex); + walkLeft = true; + } else { + result.push_back(key[currentIndex]); + int i = keyIndexStack.top(); + keyIndexStack.pop(); + if (i != currentIndex) + result.push_back(key[i]); + if (keyIndexStack.empty()) + break; + currentIndex = keyIndexStack.top(); + } + } + } + return result; } - return H; -} +}; -std::vector<int> rabin_karp(const Data& input) { - string T = input.text; - string P = input.pattern; - int p = 1000000007; - int x = 1 + (rand() % static_cast<int>(1000000006)); - std::vector<int> positions; - ull pHash = poly_hash(P, p, x); - std::vector<ull> H = pre_compute_hashes(T, P.size(), p, x); - for (size_t i = 0; i < T.size() - P.size() + 1; i++) { - if (pHash != H[i]) { - continue; +void print(vector<int> a) { + for (size_t i = 0; i < a.size(); i++) { + if (i > 0) { + cout << ' '; } - if (T.compare(i, P.size(), P) == 0) - positions.push_back(i); + cout << a[i]; } - return positions; + cout << '\n'; } -//TEST(RabinKarp, t) { -// Data data; -// data.pattern = "a"; -// data.text = "ab"; -// std::vector<int> results = rabin_karp(data); -// -// ASSERT_EQ(1, results.size()); -// ASSERT_EQ(0, results[0]); -// -// data.pattern = "aba"; -// data.text = "abacaba"; -// results = rabin_karp(data); -// -// ASSERT_EQ(2, results.size()); -// ASSERT_EQ(0, results[0]); -// ASSERT_EQ(4, results[1]); -//} + +//TEST(TreeTraversal, t) { +// TreeOrders t; +// t.key = {4, 2, 5, 1, 3}; +// t.left = {1, 3, -1, -1, -1}; +// t.right = {2, 4, -1, -1, -1}; // -//TEST(RabinKarp, t1) { -// Data data; -// data.pattern = "Test"; -// data.text = "testTesttesT"; -// std::vector<int> results = rabin_karp(data); +// vector<int> results = t.in_order(); +// ASSERT_EQ(5, results.size()); +// ASSERT_EQ(1, results[0]); +// ASSERT_EQ(2, results[1]); +// ASSERT_EQ(3, results[2]); +// ASSERT_EQ(4, results[3]); +// ASSERT_EQ(5, results[4]); // -// ASSERT_EQ(1, results.size()); +// results = t.pre_order(); +// ASSERT_EQ(5, results.size()); // ASSERT_EQ(4, results[0]); -//} -// -//TEST(RabinKarp, t2) { -// Data data; -// data.pattern = "aaaaa"; -// data.text = "baaaaaaa"; -// std::vector<int> results = rabin_karp(data); +// ASSERT_EQ(2, results[1]); +// ASSERT_EQ(1, results[2]); +// ASSERT_EQ(3, results[3]); +// ASSERT_EQ(5, results[4]); // -// ASSERT_EQ(3, results.size()); +// results = t.post_order(); +// ASSERT_EQ(5, results.size()); // ASSERT_EQ(1, results[0]); -// ASSERT_EQ(2, results[1]); -// ASSERT_EQ(3, results[2]); +// ASSERT_EQ(3, results[1]); +// ASSERT_EQ(2, results[2]); +// ASSERT_EQ(5, results[3]); +// ASSERT_EQ(4, results[4]); //} -int main() { - std::ios_base::sync_with_stdio(false); - print_occurrences(rabin_karp(read_input())); - return 0; +int main_with_large_stack_space() { + ios_base::sync_with_stdio(0); + TreeOrders t; + t.read(); + print(t.in_order()); + print(t.pre_order()); + print(t.post_order()); + return 0; +} + +int main (int argc, char **argv) +{ + return main_with_large_stack_space(); } |