本文整理汇总了C++中trie类的典型用法代码示例。如果您正苦于以下问题:C++ trie类的具体用法?C++ trie怎么用?C++ trie使用的例子?那么恭喜您, 这里精选的类代码示例或许可以为您提供帮助。
在下文中一共展示了trie类的20个代码示例,这些例子默认根据受欢迎程度排序。您可以为喜欢或者感觉有用的代码点赞,您的评价将有助于我们的系统推荐出更棒的C++代码示例。
示例1: check
bool check(trie<char> &t, string s, int steps, int digits){
// cerr << s << endl;
if (steps < digits) return false;
if (steps == 0) return (bool)t.countMatches(s.begin(), s.end());
if (t.countMatches(s.begin(), s.end())) return true;
if (digits){
for (int i=0;i<s.size();i++){
if (isdigit(s[i])){
for (s[i] = 'a'; s[i] <= 'z'; s[i]++){
if (check(t, s, steps-1, digits-1)) return true;
}
for (s[i] = 'A'; s[i] <= 'Z'; s[i]++){
if (check(t, s, steps-1, digits-1)) return true;
}
}
}
}
else {
for (int i=0; i<s.size()-1; i++){
swap(s[i], s[i+1]);
if (check(t, s, steps-1, digits)) return true;
swap(s[i], s[i+1]);
}
}
return false;
}
开发者ID:meysamaghighi,项目名称:Kattis,代码行数:26,代码来源:a.cpp
示例2: makeTrie
void makeTrie(void) {
map<int, hostConf>::iterator j;
string::iterator stringit;
char* temp = new char[16];
string prestring;
char* size = new char[2];
struct cidrprefix tempFix;
for(j = routerEnd.begin(); j != routerEnd.end(); j++) {
prestring = (j->second).overlayPrefix;
for(stringit = prestring.begin(); stringit != prestring.end(); stringit++) {
if(*stringit == '/') {
strcpy(temp, prestring.substr(0, distance(prestring.begin(),stringit)).c_str());
cout << "Temp: " << temp << endl;
inet_pton(AF_INET, temp, (void *)&tempFix.prefix);
stringit++;
size[0] = *stringit;
stringit++;
size[1] = *stringit;
break;
}
}
tempFix.size = (char)atoi(size);
#ifdef DEBUG
cout << "Prefix: " << tempFix.prefix << "/" << (int)tempFix.size << " for router: " << routerIPs[j->first] << endl;
#endif
hosts.insert(tempFix, routerIPs[j->first]);
#ifdef DEBUG
cout << "Testing trie." << endl;
int testaddr;
inet_pton(AF_INET, "1.2.3.1", (void *)&testaddr);
cout << testaddr << hosts.search(testaddr) << endl;
#endif
}
}
开发者ID:Oscillope,项目名称:CS-3516-Project-3,代码行数:35,代码来源:overlay.cpp
示例3: main
/**
* Conducts behavior described in "Find Strings" problem
*/
int main (){
int n,q;
cin >> n; //get n
if((n < 1) || (n > 50)){
cout << "INVALID"; //1<=n<=50
return 0;
}
string mystr;
for(int i = 0; i < n; i++){
cin >> mystr; //get string
if((mystr.length() > 2000) || (mystr.length() < 1)){
cout << "INVALID"; //1<=mi<=2000
return 0;
}
else{
trie.insert(mystr);
}
}
trie.print();
trie.enum_substrings(substrings);
sort(substrings.begin(), substrings.end());
it = unique(substrings.begin(), substrings.end());
substrings.resize(it - substrings.begin());
print_elements(substrings);
cin >> q; //get q
if((q < 1) || (q > 500)){
cout << "INVALID"; //1<=q<=500
return 0;
}
else{
int myk;
for(int i = 0; i < q; i++){
cin >> myk; //get substring index
if(myk > substrings.size() || ((myk > 1000000000) || (myk < 1))){
kstrings.push_back("INVALID"); //1<=k<=1000000000
}
else{
kstrings.push_back(substrings[myk - 1]);
}
}
print_elements(kstrings);
}
return 0;
}
开发者ID:znameroski,项目名称:IS,代码行数:61,代码来源:FindStrings.cpp
示例4: operator
void operator()(trie<suffix_payload> & t) {
t.payload.is_orig = false;
t.payload.is_rev = false;
if (t.ch == END1) {
t.payload.is_orig = true;
return;
}
if (t.ch == END2) {
t.payload.is_rev = true;
return;
}
for (auto i = t.children.begin(); i != t.children.end(); ++i) {
if (i->second.payload.is_orig) {
t.payload.is_orig = true;
}
if (i->second.payload.is_rev) {
t.payload.is_rev = true;
}
}
if (t.payload.is_orig && t.payload.is_rev) {
if (t.payload.depth > 1) {
cout << t.path() << endl;
}
}
}
开发者ID:Mortal,项目名称:dADS2-opg5,代码行数:25,代码来源:dADS2-09-5b.cpp
示例5: total_size
/// \brief Returns size and total sum of symbols
template <typename T> std::pair<size_t, size_t> total_size(trie<T> const & t) {
size_t count = 0;
size_t total_count = 0;
t.for_each([&count, &total_count](std::vector<T> const & w) {
++count;
total_count += w.size();
});
return {count, total_count};
}
开发者ID:jamella,项目名称:learning-fuzzing,代码行数:10,代码来源:trie.hpp
示例6: main
int main()
{
freopen ("input.txt", "r", stdin);
scanf ("%d", &n); getchar();
bool new_sentence = false;
while(n--)
{
char c = 0;
do
{
c = getchar();
if (c == EOF)
break;
else if (!isalnum(c) && new_sentence)
continue;
else if (c == '?')
{
new_sentence = true;
//flush
printf ("SHIT:\n");
for (int i = 0; i < shit.size(); i++)
putchar (shit[i]); putchar('\n');
sentence_count += _trie.flush();
shit.clear();
}
else if (c == '.' || c == '!')
{
new_sentence = true;
}
else if (c != '\n')
{
shit.push_back(c);
}
} while (c != '\n');
if (c == EOF)
break;
}
printf ("sentence_count: %d\n", sentence_count);
return 0;
}
开发者ID:elvircrn,项目名称:ccppcodes,代码行数:50,代码来源:jump.cpp
示例7: find
void find(string &str, int pos, int bitm, ll lvl = 0){
bitmask |= bitm;
if(bitmask == finalbit){
res = max(res, lvl);
}
if(pos == str.length() or lvl > 60){
return;
}
if(str[pos] == 'a'){
if(a == NULL){
a = new trie;
}
a->find(str, pos + 1, bitm, lvl + 1);
} else {
if(b == NULL){
b = new trie;
}
b->find(str, pos + 1, bitm, lvl + 1);
}
}
开发者ID:ReaLNeroM,项目名称:Competitive-Programming,代码行数:24,代码来源:Trie.cpp
示例8: flatten
/// \brief Flattens a trie \p t
/// \returns an array of words (without the prefixes)
template <typename T> std::vector<std::vector<T>> flatten(trie<T> const & t) {
std::vector<std::vector<T>> ret;
t.for_each([&ret](std::vector<T> const & w) { ret.push_back(w); });
return ret;
}
开发者ID:jamella,项目名称:learning-fuzzing,代码行数:7,代码来源:trie.hpp
示例9: main
int main()
{
cout<<"KOAKSODKASdokasdo\n";
_trie = trie();
for (int i = 0; i < 500100; i++)
finished [i] = turns_into [i] = -1;
scanf ("%d", &n); getchar();
for (int i = 0; i < n; i++)
_trie.parse_input();
for (int i = 0; i < words.size(); i++)
printf ("%d ", words [i]); printf ("\n");
scanf ("%d", &m); getchar();
for (int i = 0; i < m; i++)
{
int X = _trie.parse_input();
int Y = _trie.parse_input();
printf ("%d %d\n", X, Y);
turns_into[X] = Y;
cool [X] = true;
QMAX = max (X, Y);
}
QMAX = max (QMAX, word_index);
int R = 0, L = 0;
for (int i = 0; i < words.size(); i)
{
if (turns_into [words [i]] == -1)
{
R += R_count [words [i]];
L += lengths [words [i]];
}
else if (finished [words [i]])
{
R += R_count [words [i]];
L += lengths [words [i]];
}
else
{
stacks.clear();
int current_index = words [i];
int q = i - 1;
while (finished [current_index] != -1)
{
stacks.push_back(current_index);
finished[current_index] = 1;
current_index = turns_into [current_index];
}
stacks.push_back(current_index);
int MAXR = R_count[current_index];
int MAXL = lengths[current_index];
for (int j = stacks.size() - 2; j > -1; j--)
{
if (R_count [stacks [j]] == R_count [stacks [j - 1]])
{
R_count[stacks [j]] = R_count[stacks [j + 1]];
}
}
}
}
return 0;
}
开发者ID:elvircrn,项目名称:ccppcodes,代码行数:76,代码来源:D+(15).cpp
示例10: test_callback2
cout <<"test callback 1" << endl;
return true;
}
bool test_callback2(){
cout <<"test callback 2" << endl;
return true;
}
bool test_callback3(){
cout <<"test callback 3" << endl;
return false;
}
TEST_CASE( "trie", "[trie]" ) {
bool bRet;
trie<int, std::function<bool(void)> > _trie;
SECTION( "insert and retrieve items" ) {
queue< int > keys1;
keys1.push(3);
keys1.push(1);
queue< int > keys2;
keys2.push(3);
keys2.push(5);
keys2.push(0);
queue< int > keys3;
keys3.push(7);
std::function<bool(void)> f1 = test_callback1;
开发者ID:bilbil,项目名称:enhance,代码行数:31,代码来源:test_trie.cpp
示例11: WordFilter
WordFilter(vector<string> words) {
for (int i = 0; i < words.size(); i++) {
t_prefix.insert(words[i], i);
reverse(words[i].begin(), words[i].end());
t_suffix.insert(words[i], i);
}
}
开发者ID:seven-gao,项目名称:alg,代码行数:7,代码来源:prefix_and_suffix_search.cpp
示例12: generate
void generate(string s, int val)
{
queue<string> q;
int i, h, pai, filho;
if(m.count(s) == 0)
{
m[s] = m.size() - 1;
q.push(s);
}
pai = m[s];
tam[pai] = val;
while(!q.empty())
{
s = q.front();
pai = m[s];
q.pop();
if(tam[pai] > resp) continue;
query.clear();
t.match(s, 0);
for(i=0;i<query.size();i++)
{
if(!sufix(s, query[i])) continue;
if(m.count(sufstr) == 0)
{
m[sufstr] = m.size() - 1;
filho = m.size() - 1;
q.push(sufstr);
}
else filho = m[sufstr];
tam[filho] = tam[pai] + sufdis;
grafo[pai].push_back(filho);
peso[pai].push_back(sufdis);
}
}
}
开发者ID:jccarvalhosa,项目名称:maratona,代码行数:35,代码来源:ambiguos.cpp
示例13: AutocompleteSystem
AutocompleteSystem(vector<string> sentences, vector<int> times) {
for (int i = 0; i < sentences.size(); i++) {
for (int j = 0; j < times[i]; j++)
tr.insert(sentences[i]);
}
node = &tr;
}
开发者ID:seven-gao,项目名称:alg,代码行数:7,代码来源:design_search_autocomplete_system.cpp
示例14: main
int main()
{
while (true)
{
scanf("%d%d",&n,&m);
if (n == 0 && m == 0) break;
ac.init();
for (int i = 0; i < n; i++)
{
scanf("%s",buf);
ac.insert(buf,i);
}
for (int i = 0; i < m; i++)
{
scanf("%s",buf);
ac.insert(buf,-1);
}
ac.build();
tot = 0;
pos[tot++] = 0;
for (int i = 0; i < ac.L; i++)
if (ac.endv[i] == false && ac.endr[i] != 0)
pos[tot++] = i;
for (int i = 0; i < tot; i++)
Gao(i);
memset(dp,-1,sizeof(dp));
dp[0][0] = 0;
for (int i = 0; i < (1<<n); i++)
for (int j = 0; j < tot; j++)
if (dp[i][j] != -1)
for (int k = 0; k < tot; k++)
if (d[j][k] != -1)
{
int newsta = i|ac.endr[pos[k]];
if (dp[newsta][k] == -1 || dp[newsta][k] > dp[i][j]+d[j][k])
dp[newsta][k] = dp[i][j]+d[j][k];
}
int res = -1;
for (int i = 0; i < tot; i++)
if (dp[(1<<n)-1][i] != -1)
if (res == -1 || res > dp[(1<<n)-1][i])
res = dp[(1<<n)-1][i];
printf("%d\n",res);
}
return 0;
}
开发者ID:mzry1992,项目名称:workspace,代码行数:46,代码来源:Resource+Archiver.cpp
示例15: main
int main()
{
int N, i, j, k;
vector<string> init;
vector<int> start;
string str;
char s[100];
while(scanf("%d", &N) != EOF && N)
{
v.clear();
init.clear();
start.clear();
t.children.clear();
for(i=0;i<m.size();i++)
{
grafo[i].clear();
peso[i].clear();
tam[i] = INF;
}
m.clear();
m[""] = 0;
for(i=0;i<N;i++)
{
scanf("%s", s);
t.insert(s, 0);
v.push_back(s);
}
for(i=0;i<v.size();i++)
{
query.clear();
t.match(v[i], 0);
for(j=0;j<query.size();j++) if(query[j] != v[i])
{
if(!sufix(v[i], query[j])) continue;
init.push_back(sufstr);
start.push_back(max(v[i].size(), query[j].size()));
}
}
resp = INF;
for(i=0;i<init.size();i++) if(start[i] < resp) resp = min(resp, shortest_path(init[i], start[i]));
if(resp == INF) printf("-1\n");
else printf("%d\n", resp);
}
return 0;
}
开发者ID:jccarvalhosa,项目名称:maratona,代码行数:45,代码来源:ambiguos.cpp
示例16: input
vector<string> input(char c) {
vector<string> r;
if (c == '#') {
tr.insert(s);
s.clear();
node = &tr;
return r;
}
s.push_back(c);
if (node != nullptr) {
node = node->get_next(c);
if (node != nullptr)
return node->get_top3();
}
return r;
}
开发者ID:seven-gao,项目名称:alg,代码行数:20,代码来源:design_search_autocomplete_system.cpp
示例17: f
int f(string prefix, string suffix) {
auto p = t_prefix.find(prefix);
reverse(suffix.begin(), suffix.end());
auto q = t_suffix.find(suffix);
if (p == nullptr || q == nullptr) return -1;
auto m = p->get();
auto n = q->get();
int i = m.size()-1;
int j = n.size()-1;
while (i>= 0 && j >= 0 && m[i] != n[j]) {
if (m[i] > n[j]) {
i--;
}
else {
j--;
}
}
if (i >= 0 && j >= 0 && m[i] == n[j])
return m[i];
return -1;
}
开发者ID:seven-gao,项目名称:alg,代码行数:23,代码来源:prefix_and_suffix_search.cpp
示例18: main
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
finalbit = (1 << n) - 1;
for(int i = 0; i < n; i++){
string str;
cin >> str;
for(int j = 0; j < str.length(); j++){
root.find(str, j, 1 << i);
}
}
cout << res;
return 0;
}
开发者ID:ReaLNeroM,项目名称:Competitive-Programming,代码行数:19,代码来源:Trie.cpp
示例19: calc
void calc() {
t.pre_order_traversal(depth_calc());
t.post_order_traversal(lsr_calc());
}
开发者ID:Mortal,项目名称:dADS2-opg5,代码行数:4,代码来源:dADS2-09-5b.cpp
示例20: set_string
void set_string(string s) {
t.insert_suffixes(s + END1);
t.insert_suffixes(string(s.rbegin(), s.rend()) + END2);
}
开发者ID:Mortal,项目名称:dADS2-opg5,代码行数:4,代码来源:dADS2-09-5b.cpp
注:本文中的trie类示例由纯净天空整理自Github/MSDocs等源码及文档管理平台,相关代码片段筛选自各路编程大神贡献的开源项目,源码版权归原作者所有,传播和使用请参考对应项目的License;未经允许,请勿转载。 |
请发表评论