S.M.
BAN USERMy solution in C++
#include <iostream>
#include <string>
bool isPeriodic(const std::string& str) {
std::string test = str.substr(1) + str.substr(0, str.length() / 2);
return test.find(str) != test.npos;
}
auto findPeriod(const std::string& str) {
auto len = 0;
std::string test = str.substr(1) + str.substr(0, str.length() / 2);
while (test.find(str) != test.npos) {
++len;
test.erase(test.length() - 1);
}
if (!len)
return std::string();
return str.substr(0, 1 + str.length() / 2 - len);
}
Suppose N is less than large paragraph length M. O(M) time is required.
#include <unordered_map>
#include <string>
#include <deque>
#include <iostream>
class Slider {
public:
Slider(const std::deque<std::string>& para, const std::deque<std::string>& words) : para_(para) {
if (para.size() < words.size())
return;
for (auto& w : words)
words_[w]++;
words_left_ = words.size();
min_para_ = std::make_pair(0, -1);
}
bool next_word() {
if (!words_left_) {
next_site();
}
if (idx_ >= para_.size())
return false;
auto w = para_[idx_++];
auto it = words_.find(w);
if (it == words_.end()) {
if (length_ == 0) {
// if slider is empty then start with the next word; this condition can be removed.
++site_;
return true;
} else {
++length_;
}
} else {
++length_;
// negative is ok, but if positive then less words left to find
if ((--it->second) >= 0) {
--words_left_;
}
}
return true;
}
int site() const {
return min_para_.first;
}
int length() const {
return min_para_.second;
}
private:
void next_site()
{
while (!words_left_) {
// if no words to find left then check if new subparagraph is less than prev one
if (min_para_.second == -1 || min_para_.second > length_) {
min_para_.first = site_;
min_para_.second = length_;
}
// try move slider right
--length_;
auto w = para_[site_++];
auto it = words_.find(w);
if (it != words_.end() && (++it->second) > 0) {
++words_left_;
}
}
}
const std::deque<std::string> ¶_;
std::unordered_map<std::string, int> words_; // words and word counts
int words_left_; // number of words left to find
int site_ = 0; // slider start
int length_ = 0; // slider length
int idx_ = 0; // next word following slider
std::pair<int, int> min_para_; // subparagraph idx and length
};
int main() {
std::deque<std::string> para = {"alpha", "beta", "gamma", "beta", "aba", "beta", "zeta", "beta", "zen", "cat", "car", "beta", "aba", "beta", "broad"};
std::deque<std::string> words = {"aba", "beta", "cat", "beta"};
Slider slider(para, words);
while (slider.next_word())
;
if (slider.length() > 0)
std::cout << "Min subparagraph length is " << slider.length() << std::endl;
}
C++
#include <string>
#include <locale>
#include <iostream>
std::locale loc("C");
std::string::const_iterator expanded(const std::string &str, std::string::const_iterator start, std::string &out) {
while (start != str.end()) {
if (std::isalpha(*start, loc))
out.push_back(*start++);
else if (std::isdigit(*start)) {
char *end = nullptr;
auto cnt = std::strtol(&*start, &end, 10);
if (cnt == 0 || *end != '[')
return str.end();
start += end - &*start + 1;
std::string::const_iterator ret;
for (; cnt > 0; --cnt)
ret = expanded(str, start, out);
start = ret;
}
else if (*start == ']')
return start + 1;
}
return start;
}
std::string expanded(const std::string &str)
{
std::string res;
expanded(str, str.begin(), res);
return res;
}
int main() {
auto r = expanded("a2[bc2[c]]d");
auto expected = "abcccbcccd";
std::cout << "\"" << r << "\" == \"" << expected << "\" is " << std::boolalpha << (r == expected) << std::endl;
}
Using tree.
#include <string>
#include <memory>
#include <iostream>
class Node {
public:
Node(const std::string &word) : word_(word) {}
const std::string &word() const { return word_; }
static void insertWord(std::unique_ptr<Node> &tree, const std::string &word)
{
if (tree.get() == nullptr)
tree.reset(new Node(word));
else if (word < tree->word())
insertWord(tree->childs_[0], word);
else
insertWord(tree->childs_[1], word);
}
std::string findNextWord(const std::string &word)
{
if (word < word_) {
std::string w;
if (childs_[0])
w = childs_[0]->findNextWord(word);
return w.empty() ? word_ : w; // if less than me not found then return me
} else {
if (!childs_[1])
return std::string(); // not found
return childs_[1]->findNextWord(word);
}
}
private:
std::string word_;
std::unique_ptr<Node> childs_[2];
};
int main() {
std::unique_ptr<Node> tree;
for (decltype(auto) w : {"cat", "dog", "cow", "donkey", "zebra", "monkey"})
Node::insertWord(tree, w);
std::string w;
while (true)
{
std::cout << "Input: ";
std::cin >> w;
if (std::cin.eof())
break;
std::cout << "Output: " << tree->findNextWord(w) << std::endl;
}
}
#include <vector>
#include <algorithm>
int getRundom19(); // returns random number from 1 till 9
int getRundom18(); // returns random number from 1 till 8
int getRundomEven08(); // returns rundom even number from 0 till 8
int getNumber() {
std::vector<int> digits(10);
std::iota(digits.begin(), digits.end(), 0);
int dig = getRundomEven08();
int num = dig; // lowest even digit from 0 till 8
for (int mul = 10; mul <= 100; mul *= 10) {
std::swap(digits[0], digits[dig]); // digits[0] contains adjacent digit
int d = digits[getRundom19()]; // random digit of digits[1] till digits[9]
num += d * mul;
std::swap(digits[0], digits[dig]); // digits again is {0 .. 9}
dig = d;
}
std::swap(digits[9], digits[dig]); // digits[9] contains adjacent digit, digits[0] contains useless 0
dig = digits[getRundom18()];
num += dig * 1000;
return num;
}
#include <stack>
#include <iostream>
class MinStack {
public:
void push(int n) {
stack_.push(n);
// track all multiple min values
if (min_stack_.empty() || n <= min_stack_.top())
min_stack_.push(n);
}
void pop() {
if (stack_.empty())
return;
auto n = stack_.top();
stack_.pop();
if (n == min_stack_.top())
min_stack_.pop();
}
int top() {
return stack_.top();
}
int min() {
return min_stack_.top();
}
bool empty() {
return stack_.empty();
}
private:
std::stack<int> stack_;
std::stack<int> min_stack_;
};
int main() {
MinStack stack;
for (auto n : {10, 9, 20, 8, 8, 30, 8, 7}) {
stack.push(n);
std::cout << "stack.top() is " << stack.top() << ", stack.min() is " << stack.min() << std::endl;
}
std::cout << std::endl;
while (!stack.empty())
{
std::cout << "stack.top() is " << stack.top() << ", stack.min() is " << stack.min() << std::endl;
stack.pop();
}
}
#include <list>
#include <unordered_set>
struct Node {
int ID = 0; // >= 0
int parentID = -1; // no parent
};
// Create a hash set to store traversing nodes.
// Insert node[i] into the set once node[i] has its parent in the set.
// If parent of node[i] is not found in the set, then the list is not given in preorder.
bool IsInPreorder(const std::list<Node> &list) {
if (list.empty())
return true;
if (list.size() == 1)
return list.front().parentID == -1;
std::unordered_set<decltype(Node::parentID)> parents;
parents.insert(list.front().ID);
auto i = list.begin();
for (++i; i != list.end(); ++i) {
if (parents.find(i->parentID) == parents.end())
return false;
parents.insert(i->ID);
}
return true;
}
Repgarycsroka, Backend Developer at Axiom Sources
Hi I’m Gary, an average 19 year old in a state college who sees life as an adventure.Provide ...
Alternative solution for findPeriod in C++
- S.M. January 20, 2018