3
すべての一意のサブストリングを印刷する必要があります。だから私はtrieを構築するが、どのように私はすべてのサブ文字列を印刷することができないのか把握することができません。 たとえば、入力がaabとaacの場合は、"a", "aa", "aab", "aac", "ab", "ac", "b", "c"と表示されます。データ構造とすべてのサブストリングを印刷する
基本的には、文字列のセットから一意の部分文字列を取得する方法を見つける必要があります。私は考えているtrieは良い方法ですtrieを取るだろうO(n)
私のコードはトライを構築することです。
#include <string>
#include <iostream>
#include <vector>
struct trie_node {
trie_node *(next[26]);
trie_node() {
for (int i = 0; i < 26; ++i) {
next[i] = (trie_node*)0;
}
}
};
trie_node *root;
char cur_substring[2000];
void build_trie(std::string& input) {
trie_node *ptrie = root;
for (std::string::iterator it = input.begin(); it != input.end(); ++it) {
int i = *it - 'a';
if (ptrie->next[i] == (trie_node*)0)
ptrie->next[i] = new trie_node;
ptrie = ptrie->next[i];
}
}
void print_sub_strings(trie_node *p_trie, int pos) {
for (int i = 0; i < 26; i++) {
if (p_trie->next[i] != (trie_node*)0) {
cur_substring[pos] = i + 'a';
print_sub_strings(p_trie->next[i], pos + 1);
}
}
}
UPDATE 1
私は私のコードを再書いなった入力に基づいてが、また、動作しているようですしません。あなたが適切にあなたの元の文字列のすべての可能なサブ文字列を与えるトライをトラバース、すべての文字列を考慮してトライ構造を構築した場合
#include <string>
#include <iostream>
#include <vector>
const int ALPHABET_SIZE = 26;
char text[2000];
int LEN;
struct trie_node_t {
trie_node_t*child_list[ALPHABET_SIZE];
trie_node_t() {
for(int index = 0; index < ALPHABET_SIZE; index++)
child_list[index] = (trie_node_t*)0;
}
};
class Trie {
public:
Trie():m_root(new trie_node_t) {
}
~Trie() {
_delete(m_root);
}
void _insert(int pos) {
int lcv, index;
trie_node_t* t = m_root;
for(lcv = pos; lcv < LEN; lcv++) {
index = text[lcv] - 'a';
if (t->child_list[index] == (trie_node_t*)0) {
t->child_list[index] = new trie_node_t;
}
t = t->child_list[index];
}
}
void insert() {
for (int i = 0; i < LEN; i++) {
_insert(i);
}
}
void iterate() {
_iterate(m_root, "");
}
void _iterate(trie_node_t *t, std::string prefix) {
for (int i = 0; i < ALPHABET_SIZE; i++) {
if (t->child_list[i] != (trie_node_t*)0) {
prefix += 'a' + i;
std::cout << prefix << std::endl;
_iterate(t->child_list[i], prefix);
}
}
}
private:
int node_count;
trie_node_t* m_root;
void _delete (trie_node_t* t) {
int index;
if (t != (trie_node_t*)0) {
for(index = 0; index < ALPHABET_SIZE; index++)
_delete(t->child_list[index]);
delete t;
}
}
};
int main (int argc, char** argv) {
Trie *pTrie = new Trie();
strcpy(text,"aab");
LEN = strlen(text);
pTrie->insert();
strcpy(text,"aac");
LEN = strlen(text);
pTrie->insert();
pTrie->iterate();
}
出力は、
a
aa
aab
aabc
aab
aabc
ab
abc
Press any key to continue . . .
一部の文字列にはO（n^2）個の部分文字列が含まれているため、O（n）時間内にすべての部分文字列を出力することはできません。たとえば、abcdefg ... zとなります。 – templatetypedef
@templatetypedef、私は同意しますが、トライの繰り返しはすべて私にすべての部分文字列を与えるでしょう。私がトライ絵を描くと、ツリーを正しくトラバースすればすべての部分文字列を得ることができます。 – Avinash
コードの最初の追加コメント：_または__で始まる識別子は使用しないでください。 _と__で始まるすべての識別子は予約されています。また、あなたのコードはあなたが定期的にCをやっているように見え、現在C++をやっています。 C++のイディオムを学ぼうとすると、多くの場合、本当に役立ちます。 – LiKao