输入数字n,输入n个字符串。输入一个字符串s。s由这n个字符串组成。输出最少需要的字符串。样例输入:3 a bc d abcdbc 输出:4C++
时间: 2024-03-10 19:51:07 浏览: 51
使用C++,实现从输入流中分析出数字串。
好的,这里是C++代码实现。请注意,我使用了STL库中的unordered_map来实现Trie树。
```cpp
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
struct TrieNode {
unordered_map<char, TrieNode*> children;
bool is_end;
TrieNode() : is_end(false) {}
};
void insert(TrieNode* root, string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->is_end = true;
}
int match(TrieNode* root, string& s) {
int count = 0;
TrieNode* node = root;
for (int i = 0; i < s.length();) {
char c = s[i];
if (node->children.count(c)) {
node = node->children[c];
i++;
if (node->is_end) {
count++;
node = root;
}
} else {
return -1;
}
}
return node->is_end ? count + 1 : -1;
}
int main() {
int n;
cin >> n;
TrieNode* root = new TrieNode();
for (int i = 0; i < n; i++) {
string word;
cin >> word;
insert(root, word);
}
string s;
cin >> s;
int result = match(root, s);
cout << result << endl;
return 0;
}
```
希望能对你有所帮助!
阅读全文