Share 79. word search in c++,

[nghiadungdoan]

#C ++, #tìm kiếm từ, #search Thuật toán, #Programming, #data Cấu trúc ## 79. Tìm kiếm từ trong C ++

Trong hướng dẫn này, chúng tôi sẽ tìm hiểu cách thực hiện thuật toán tìm kiếm từ trong C ++.Trước tiên chúng tôi sẽ thảo luận về thuật toán vũ phu và sau đó chúng tôi sẽ thực hiện một thuật toán hiệu quả hơn bằng cách sử dụng cấu trúc dữ liệu Trie.

### Thuật toán vét cạn

Thuật toán vũ phu là cách đơn giản nhất để tìm kiếm một từ trong một văn bản.Nó hoạt động bằng cách lặp lại trên mỗi ký tự trong văn bản và kiểm tra xem phần phụ hiện tại có khớp với từ này không.Nếu nó làm, thì từ này đã được tìm thấy.

Sau đây là mã giả cho thuật toán vũ phu:

`` `
function word_search (văn bản, word) {
for (i = 0; i <len (văn bản); i ++) {
for (j = 0; j <len (word); j ++) {
if (text [i + j]! = word [j]) {
phá vỡ;
}
}
if (j == len (từ)) {
trả lại đúng;
}
}
trả lại sai;
}
`` `

Độ phức tạp về thời gian của thuật toán vũ phu là O (n * m), trong đó n là độ dài của văn bản và m là độ dài của từ.

### Thuật toán Trie

Thuật toán Trie là một cách hiệu quả hơn để tìm kiếm một từ trong một văn bản.Trie là cấu trúc dữ liệu cây trong đó mỗi nút đại diện cho một chữ cái.Nút gốc đại diện cho chuỗi trống và mỗi nút con đại diện cho một chữ cái.

Để tìm kiếm một từ trong một trie, chúng tôi bắt đầu ở nút gốc và lặp qua từng chữ cái trong từ.Đối với mỗi chữ cái, chúng tôi theo nút con tương ứng.Nếu chúng ta đến một nút lá, thì từ này đã được tìm thấy.

Sau đây là mã giả cho thuật toán Trie:

`` `
function word_search (trie, word) {
nút = trie;
for (i = 0; i <len (từ); i ++) {
node = node.children [word ];
if (node == null) {
trả lại sai;
}
}
if (node.is_word) {
trả lại đúng;
}
trả lại sai;
}
`` `

Độ phức tạp về thời gian của thuật toán Trie là O (M), trong đó m là độ dài của từ.

### Thực hiện

Chúng ta có thể thực hiện thuật toán vũ phu và thuật toán Trie trong C ++ như sau:

`` `C ++
#include <Istream>
#include <String>

sử dụng không gian tên STD;

// Thuật toán vét cạn
bool word_search (chuỗi văn bản, chuỗi chuỗi) {
for (int i = 0; i <text.length (); i ++) {
for (int j = 0; j <word.length (); j ++) {
if (text [i + j]! = word [j]) {
phá vỡ;
}
}
if (j == word.length ()) {
trả lại đúng;
}
}
trả lại sai;
}

// cấu trúc dữ liệu trie
Struct Trienode {
bool is_word;
Trienode* trẻ em [26];

Trienode () {
is_word = false;
for (int i = 0; i <26; i ++) {
trẻ em = null;
}
}
};

// Thuật toán Trie
Bool Word_Search (Trienode* Trie, String Word) {
Trienode* nút = trie;
for (int i = 0; i <word.length (); i ++) {
nút = nút-> trẻ em [word - 'a'];
if (node == null) {
trả lại sai;
}
}
if (nút-> is_word
=======================================
#C++, #Word search, #search algorithm, #Programming, #data structure ## 79. Word Search in C++

In this tutorial, we will learn how to implement a word search algorithm in C++. We will first discuss the brute-force algorithm, and then we will implement a more efficient algorithm using a trie data structure.

### Brute-Force Algorithm

The brute-force algorithm is the simplest way to search for a word in a text. It works by iterating over each character in the text, and checking if the current substring matches the word. If it does, then the word has been found.

The following is the pseudocode for the brute-force algorithm:

```
function word_search(text, word) {
for (i = 0; i < len(text); i++) {
for (j = 0; j < len(word); j++) {
if (text[i + j] != word[j]) {
break;
}
}
if (j == len(word)) {
return true;
}
}
return false;
}
```

The time complexity of the brute-force algorithm is O(n * m), where n is the length of the text and m is the length of the word.

### Trie Algorithm

The trie algorithm is a more efficient way to search for a word in a text. A trie is a tree data structure where each node represents a letter. The root node represents the empty string, and each child node represents a letter.

To search for a word in a trie, we start at the root node and iterate over each letter in the word. For each letter, we follow the corresponding child node. If we reach a leaf node, then the word has been found.

The following is the pseudocode for the trie algorithm:

```
function word_search(trie, word) {
node = trie;
for (i = 0; i < len(word); i++) {
node = node.children[word];
if (node == null) {
return false;
}
}
if (node.is_word) {
return true;
}
return false;
}
```

The time complexity of the trie algorithm is O(m), where m is the length of the word.

### Implementation

We can implement the brute-force algorithm and the trie algorithm in C++ as follows:

```c++
#include <iostream>
#include <string>

using namespace std;

// Brute-force algorithm
bool word_search(string text, string word) {
for (int i = 0; i < text.length(); i++) {
for (int j = 0; j < word.length(); j++) {
if (text[i + j] != word[j]) {
break;
}
}
if (j == word.length()) {
return true;
}
}
return false;
}

// Trie data structure
struct TrieNode {
bool is_word;
TrieNode* children[26];

TrieNode() {
is_word = false;
for (int i = 0; i < 26; i++) {
children = NULL;
}
}
};

// Trie algorithm
bool word_search(TrieNode* trie, string word) {
TrieNode* node = trie;
for (int i = 0; i < word.length(); i++) {
node = node->children[word - 'a'];
if (node == NULL) {
return false;
}
}
if (node->is_word