Created by Vladimir Tsvetkov on 08 07 14 clear clear -o search -std 11

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// Created by Vladimir Tsvetkov on 08/07/14.
//clear && clear && g++ -o search -std=c++11 -g search.cpp ./../../src/string/unistring.cpp
#include <iostream>
#include <string>
#include <set>
#include <map>
#include "../../include/string/unistring.h"
class trieNode
{
public:
Unistring data;
std::map<Unistring, trieNode> leaves;
bool isFinal;
trieNode();
trieNode(Unistring ndata, std::map<Unistring, trieNode> nleaves);
~trieNode();
};
class Trie
{
public:
trieNode root;
Trie();
~Trie();
std::set<Unistring> searchWordsFromTrie(Unistring pattern);
std::set<Unistring> searchWords(trieNode node, Unistring pattern, int curIndex, Unistring formedString);
};
std::set<Unistring> Trie::searchWordsFromTrie(Unistring pattern)
{
Unistring word;
std::set<Unistring> finalset = searchWords(root, pattern, 0, word);
}
int commonPrefix(Unistring data, Unistring pattern, int curIndex)
{
Unistring cutPattern = *pattern.substr(curIndex);
for(int i = 0; i < data.size(); i++)
if (i == cutPattern.size() || data[i] != cutPattern[i])
return i;
return data.size();
}
std::set<Unistring> Trie::searchWords(trieNode node, Unistring pattern, int curIndex, Unistring formedString)
{
std::cout << "searchWordsCall with curIndex " << curIndex << "\n";
if (node.isFinal && curIndex == (pattern.size() - 1))
{
std::set<Unistring> wordSet;
wordSet.insert(formedString);
return wordSet;
}
std::set<Unistring> wordSet;
Unistring curChar = *pattern.substr(curIndex, curIndex + 1);
if (curChar.compare_to())
{
Unistring newformedString = formedString;
wordSet.insert(searchWords(node, pattern, curIndex + 1, newformedString));
for(auto i:node.leaves)
{
Unistring newnewformedString = formedString;
wordSet.insert(searchWords(i.second, pattern, curIndex, newnewformedString));
}
return wordSet;
} else
{
int commonPrefixsize = commonPrefix(node.data, pattern, curIndex);
//Unistring commonPrefix = node.data.substring(0, commonPrefixsize);
trieNode nextNode;
if (commonPrefixsize == node.data.size())
{
//поиск от ребенка
nextNode = node.leaves[pattern[commonPrefixsize]];
} else
{
//сплитим ноду
Unistring newData = node.data.substr(commonPrefixsize);
std::map<Unistring, trieNode> newleaves = node.leaves;
nextNode = trieNode(newData, newleaves);
}
wordSet.insert(searchWords(nextNode, pattern, curIndex + commonPrefixsize, formedString + node.data));
return wordSet;
}
}
Unistring c_str_to_Unistring(std::string str)
{
Utf8String strseq = Utf8String((char*)strseq)
}
void test()
{
std::set<Unistring> resultset;
//Unistring pattern = "ab*ra*";
std::string pattern;
std::cin >> pattern;
//std::cout << "pattern:\n" << pattern << "\n";
Utf8String patternseq = Utf8String((char*)pattern.c_str());
Unistring patternunistring = Unistring(patternseq);
std::cout << "pattern:\n";
patternunistring.print();
std::cout << "\n";
Unistring *substr = patternunistring.substr(0, 2);
substr->print();
//resultset.insert(pattern);
//Trie trie;
//resultset = trie.searchWordsFromTrie(pattern);
//for(auto i:resultset)
//std::cout << i;
}
int main(int argc, const char * argv[])
{
test();
return 0;
}