lesit.jae
BAN USERI think the most important thing is to get the set of lengths.
The available length is a prime of string length and all length are combination of the primes.
If you find a prime up to square root of the string length, you can find another prime.
Then, the time complexity to get the set of lengths is O(square root of N), N is the string length.
The maximum number of the set of length is 2 X square root of N.
Therefore, the total time complexity is O(square root of N)
bool isPeriodic(const string& str, int len)
{
for (int i = len, last = str.size() - len -1; i < last; i += len)
{
for (int k = 0; k < len; k++) {
if (str[k] != str[i + k])
return false;
}
}
return true;
}
string findPeriodic(const string& str)
{
int size = str.size();
list<int> lengths = { 1 };
for (int len = 2, max_len = sqrt(size); len <= max_len; len++)
{
if (size % len == 0) {
lengths.push_back(len);
lengths.push_back(size/len);
}
}
for (int len : lengths)
{
if (isPeriodic(str, len))
return str.substr(0, len);
}
return str;
}
int main()
{
string s[] = { "ababab", "xxxxxx", "aabbaaabba" };
for (int i = 0; i < _countof(s); i++)
cout << findPeriodic(s[i]) << endl;
return 0;
}
I also thought storing all patterns into hash table.
But, there are a lot of cases of the patterns. Using the memory space will increase terribly.
I thought using the Trie could be efficient. So, modified trie.
class ClosetTrie
{
class Node;
typedef unordered_map<char, Node*> _children;
class Node
{
public:
_children children;
~Node()
{
for (pair<const char, Node*>& child : children)
delete child.second;
}
void insert(const char* str)
{
if (*str == '\0')
children['\0'] = NULL;
else
{
_children::const_iterator it = children.find(*str);
Node* child;
if (it == children.end())
{
child = new Node;
children[*str] = child;
}
else
child = it->second;
child->insert(str + 1);
}
}
void find(const char* str, int diff, const string& prefix, list<string>& ret)
{
if (ret.size() >= 3)
return;
_children::const_iterator it = children.find(*str);
if (it != children.end())
{
if (*str == '\0')
{
ret.push_back(prefix);
}
else
it->second->find(str + 1, diff, prefix + *str, ret);
}
if (diff == 0)
return;
const char* next = *str == '\0' ? str : str + 1;
--diff;
for (pair<const char, Node*>& child : children)
{
if(child.first!=*str)
child.second->find(next, diff, prefix + child.first, ret);
}
}
};
Node root;
public:
ClosetTrie(const unordered_set<string>& dict)
{
for (const std::string& str : dict)
root.insert(str.c_str());
}
void find(const char* word, list<string>& ret)
{
root.find(word, 1, "", ret);
}
};
int main()
{
ClosetTrie trie({ "vil", "sit", "flick", "pat", "pluck", "sat", "vat" });
list<string> closets;
trie.find("vit", closets);
return 0;
}
struct PathNode
{
shared_ptr<PathNode> prev;
int dist;
const GraphNode* node;
PathNode(const GraphNode* n, shared_ptr<PathNode>* p=NULL)
{
node = n;
if (p)
{
prev = *p;
dist = p->get()->dist + 1;
}
else
dist = 0;
}
bool has(const GraphNode* f)
{
PathNode* cur = this;
do {
if (cur->node == f)
return true;
cur = cur->prev.get();
} while (cur);
return false;
}
void getAllPath(list<const GraphNode*>& ret)
{
PathNode* cur = this;
do {
ret.push_front(cur->node);
cur = cur->prev.get();
} while (cur);
}
};
void findShortestCycle(const GraphNode& node, list<const GraphNode*>& ret)
{
queue<shared_ptr<PathNode>> to_visit;
to_visit.push(shared_ptr<PathNode>(new PathNode(&node)));
unordered_map<const GraphNode*, int> dist_map;
while (!to_visit.empty())
{
shared_ptr<PathNode> path = to_visit.front(); to_visit.pop();
cout << to_visit.size() << ":" << path->node->getValue() << " -> ";
for (const GraphNode* linked : path->node->links())
{
cout << linked->getValue();
if (path->has(linked)) // cycle
{
cout << endl;
path->getAllPath(ret);
return;
}
unordered_map<const GraphNode*, int>::iterator dist_it = dist_map.find(linked);
if (dist_it != dist_map.end() && dist_it->second < path->dist + 1)
{
cout << "-skip";
continue;
}
cout << " ";
shared_ptr<PathNode> new_path(new PathNode(linked, &path));
to_visit.push(new_path);
dist_map.insert({ linked, new_path->dist });
}
cout << endl;
}
}
void TestShortCycle()
{
/*
b --+ d
+ | \
/ | \
/ + +
a ------+ c +----- f
\ +
\ /
+ /
e
cycle1 : a -> b -> d -> c -> e -> f -> c
cycle2 : a -> c -> e -> f -> c
the lengths of two path are same until 'f' node : a -> b -> d -> f, a -> c -> e -> f
so, we can't use dijkstra's algorithm to calcuate shortest cycle.
we can't use visited hash table neither.
If you use it, second path(a -> c -> e -> f) will vanish.
But, I really want the faster way of checking cycle
*/
GraphNode a("a"), b("b"), c("c"), d("d"), e("e"), f("f");
a.addFriend(&b);
a.addFriend(&c);
b.addFriend(&d);
c.addFriend(&e);
d.addFriend(&f);
d.addFriend(&c);
e.addFriend(&f);
f.addFriend(&c);
list<const GraphNode*> ret;
findShortestCycle(a, ret);
cout << "path : ";
for(const GraphNode* node : ret)
cout << node->getValue() << " ";
cout << endl;
}
void subset(int* data, int n, int start, list<list<int>>& ret)
{
if (start == n)
{
ret.resize(ret.size() + 1);
return;
}
list<list<int>> with;
subset(data, n, start + 1, with); // use data[start]
for (list<int>& set : with)
set.push_front(data[start]);
list<list<int>> without;
subset(data, n, start + 1, without); // not use data[start]
ret.assign(with.begin(), with.end());
ret.insert(ret.end(), without.begin(), without.end());
}
int countSubsets(vector<int> data, int K) {
sort(data.begin(), data.end());
int count = 0;
int n = data.size();
for (int i = 0; i<n; i++) {
if (data[i]>K)
break;
int below_max = K - data[i];
for (int j = i; j<n; j++) {
if (data[j]>below_max)
break;
// if has inner set like set [{2 4 6 7}. min=2 max=7], so we consider just how many sub set with {4 6} can make
/*
2 4 6 7
2 4 7
2 6 7
2 7
is like
{4 6}
{4}
{6}
{}
*/
if (i < j)
{
int* inner_set = &data[i + 1];
int inner_n = j - i - 1;
list<list<int>> ret;
subset(inner_set, inner_n, 0, ret);
count += ret.size();
for (list<int>& sub : ret)
{
cout << data[i];
if (sub.size() > 0)
{
for (int v : sub)
cout << ", " << v;
}
cout << ", " << data[j] << endl;
}
}
else
{
++count;
cout << data[i] << endl;
}
}
}
return count;
}
int countOfTeams(int* countries, int N, int K)
{
if (K == 0 || K>N) return 0;
priority_queue<int, vector<int>> maxheap;
for (int i = 0; i < N;i++)
maxheap.push(countries[i]);
vector<int> team(K);
int sum = 0;
while (K <= maxheap.size())
{
for (int i = 0; i < K; i++)
{
team[i] = maxheap.top();
maxheap.pop();
}
int count = team.back();
sum += count;
for (int i = 0; i < K; i++)
{
team[i] -= count;
if (team[i] > 0)
maxheap.push(team[i]);
}
}
return sum;
}
typedef map<__int64, vector<std::string>> _subset_map;
void getMerges(const std::string& a, const std::string&b, const std::string& prefix, _subset_map& subsets, vector<std::string>& ret)
{
if (a.size() == 0 && b.size() == 0)
{
ret.push_back(prefix);
return;
}
__int64 key = a.size();
key = (key << 32) | b.size();
_subset_map::const_iterator f = subsets.find(key);
const vector<std::string>* sub_vector;
if (f == subsets.end())
{
vector<std::string>& sub = subsets[key];
if(a.size()>0)
getMerges(a.substr(1), b, std::string(1, a[0]), subsets, sub);
if (b.size()>0)
getMerges(a, b.substr(1), std::string(1, b[0]), subsets, sub);
sub_vector = ⊂
}
else
{
sub_vector = &(f->second);
}
for (int i = 0, n = sub_vector->size(); i<n; i++)
ret.push_back(prefix + sub_vector->at(i));
}
void getMerges(const std::string& a, const std::string& b, vector<std::string>& ret)
{
_subset_map subsets;
getMerges(a, b, "", subsets, ret);
}
#include<list>
#include<stack>
using namespace std;
enum class _ops{ins, del};
struct UndoOps
{
UndoOps(_ops ops, list<char>::const_iterator it, char ch=0)
{
this->ops=ops;
this->it=it;
this->ch=ch;
}
list<char>::const_iterator it;
_ops ops;
char ch;
};
class TextEditor
{
private:
stack<UndoOps> undo_stack;
list<char> text;
list<char>::const_iterator cur;
public:
TextEditor()
{
cur=text.end();
}
~TextEditor()
{
}
void left()
{
if(cur==text.begin()) return;
--cur;
}
void right()
{
if(cur==text.end()) return;
++cur;
}
void ins(char ch)
{
cur=text.insert(cur, ch);
undo_stack.push(UndoOps(_ops::del, cur));
++cur;
}
void backspace()
{
if(cur==text.begin()) return;
list<char>::const_iterator item=cur;--item;
char ch=*item;
cur=item;cur--;
text.erase(item);
++cur;
undo_stack.push(UndoOps(_ops::ins, cur, ch));
}
void undo()
{
if(undo_stack.empty()) return;
UndoOps undo=undo_stack.top();
undo_stack.pop();
switch(undo.ops)
{
case _ops::ins:
cur=text.insert(undo.it, undo.ch);
++cur;
break;
case _ops::del:
{
cur=undo.it;--cur;
text.erase(undo.it);
++cur;
}
break;
}
}
void print()
{
for(list<char>::const_iterator it=text.begin();it!=text.end();it++)
{
if(cur==it)
cout<<'|';
cout<<*it;
}
if(cur==text.end())
cout<<'|';
cout<<endl;
}
};
int main() {
TextEditor editor;
editor.ins('a'); editor.print();
editor.ins('b'); editor.print();
editor.ins('c'); editor.print();
editor.left(); editor.print();
editor.left(); editor.print();
editor.left(); editor.print();
editor.right(); editor.print();
editor.right(); editor.print();
editor.right(); editor.print();
editor.backspace(); editor.print();
editor.left(); editor.print();
editor.undo(); editor.print();
editor.undo(); editor.print();
editor.undo(); editor.print();
editor.undo(); editor.print();
editor.undo(); editor.print();
return 0;
}
results:
a|
ab|
abc|
ab|c
a|bc
|abc
a|bc
ab|c
abc|
ab|
a|b
abc|
ab|
a|
|
|
time complexity : n * 'search and insert of set'
= n * (2 * log n)
-> n log n
or
time complexity : log(1) + log(2) + ... + log(n)
= log(n!)
n/2 log(n/2) <= log(n!) <= n log n
so
O(n log n)
void printCoinsSum(const vector<int>& coins, int max_sum) {
int start=coins[0];
for(int i=1;i<coins.size();i++) {
if(start>coins[i])
start=coins[i];
}
set<int> coins_sum;
coins_sum.insert(0);
for(int sum=start;sum<=max_sum;sum++) {
for(int i=0;i<coins.size();i++) {
/* new_sum = coins[i] + previous values
new_sum - coins[i] = previous values
check 'new_sum - coins[i]' is in previous values
*/
if(coins_sum.find(sum-coins[i])!=coins_sum.end()) {
coins_sum.insert(sum);
break;
}
}
}
set<int>::const_iterator it=coins_sum.begin();
++it;
for(;it!=coins_sum.end();it++)
cout<<*it<<endl;
}
Repirenedpisano, Blockchain Developer at ABC TECH SUPPORT
Hello, I am Irene and I live in Pittsburgh, USA. I am working as A production worker and my duty ...
Repfrancesdpayne, AT&T Customer service email at Cavium Networks
I am Frances Payne from Jacksonville, United States. I am working as a Rental manager in Magna Gases company. I ...
Repverarfurman, Problem Setter at Cerberus Capital
I am Vera from Bullard USA, I am working as a Violin repairer in a Handyman company. My interest in ...
Reprajanadeep17, Android Engineer at 247quickbookshelp
I am a Special education teacher who adapts general education lessons and teaches various subjects to students with mild to ...
Repbradybally973, Computer Scientist at AMD
I am a network administrator. I live in Washington USA .My responsibility includes maintaining computer infrastructures with emphasis on local ...
Repbilliejeckley, SEO at Flipkart
Spent 2002-2008 testing the market for spit-takes in Los Angeles, CA. Spent 2001-2004 deploying how to get boyfriend back by ...
- lesit.jae March 29, 2019