smallelephant621
New member
Thuật toán KMP ## Thuật toán KMP trong C ++
Thuật toán Knuth-Morris-Pratt (KMP) là một thuật toán phù hợp với chuỗi tìm thấy sự xuất hiện của chuỗi mẫu trong chuỗi văn bản.Nó là một thuật toán thời gian tuyến tính, có nghĩa là thời gian chạy của nó tỷ lệ thuận với độ dài của chuỗi văn bản.
Thuật toán KMP hoạt động bằng cách đầu tiên xây dựng một bảng tiền tố của chuỗi mẫu.Bảng này được sử dụng để tăng tốc tìm kiếm mẫu trong chuỗi văn bản.Khi xảy ra sự không phù hợp, thuật toán có thể sử dụng bảng để bỏ qua một số ký tự trong chuỗi văn bản, giúp giảm số lượng so sánh cần được thực hiện.
Thuật toán KMP là một trong những thuật toán phù hợp với chuỗi hiệu quả nhất.Nó thường được sử dụng trong các trình soạn thảo văn bản, công cụ tìm kiếm và các ứng dụng khác cần tìm các mẫu trong chuỗi.
### C ++ triển khai
Sau đây là triển khai C ++ của thuật toán KMP:
`` `C ++
#include <Istream>
#include <String>
sử dụng không gian tên STD;
// Hàm này xây dựng một bảng tiền tố của chuỗi mẫu.
// Bảng được sử dụng để tăng tốc tìm kiếm mẫu trong chuỗi văn bản.
void build_prefix_table (const String & mẫu, int* bảng) {
int n = mẫu.length ();
// Khởi tạo bảng vào tất cả các số không.
for (int i = 0; i <n; i ++) {
Bảng = 0;
}
// Duy trì bảng.
for (int i = 1; i <n; i ++) {
int j = bảng [i - 1];
while (j> 0 && mẫu ! = mẫu [j]) {
J = Bảng [J - 1];
}
if (mẫu == mẫu [j]) {
Bảng = j + 1;
}
}
}
// Hàm này tìm thấy sự xuất hiện của chuỗi mẫu trong chuỗi văn bản.
// Hàm trả về một vectơ của các vị trí bắt đầu của các lần xuất hiện trong chuỗi văn bản.
Vector <Int> find_all_occurences (const String & mẫu, chuỗi const & text) {
int n = mẫu.length ();
int m = text.length ();
// Xây dựng bảng tiền tố cho chuỗi mẫu.
int* bảng = new int [n];
build_prefix_table (mẫu, bảng);
// Khởi tạo vectơ kết quả.
Kết quả vector <Int>;
// Tìm kiếm mẫu trong chuỗi văn bản.
int i = 0;
int j = 0;
while (i <m) {
while (j> 0 && text ! = mẫu [j]) {
J = Bảng [J - 1];
}
if (text == mẫu [j]) {
J ++;
}
if (j == n) {
// Chúng tôi đã tìm thấy một sự xuất hiện của mẫu.
kết quả.push_back (i - n + 1);
J = Bảng [J - 1];
}
i ++;
}
// Xóa bảng tiền tố.
xóa [] bảng;
// Trả về vectơ kết quả.
Kết quả trả lại;
}
int main () {
// Chuỗi mẫu.
chuỗi mẫu = "abcab";
// chuỗi văn bản.
Chuỗi văn bản = "Abababcabab";
// Tìm tất cả các lần xuất hiện của mẫu trong chuỗi văn bản.
Vector <Int> results = find_all_occurences (mẫu, văn bản);
// In kết quả.
for (int i = 0; i <results.size (); i ++) {
cout << kết quả << endl;
}
trả lại 0;
}
`` `
### Người giới thiệu
* [Knuth-Morris-Pratt
=======================================
KMP algorithm ## KMP Algorithm in C++
The Knuth-Morris-Pratt (KMP) algorithm is a string-matching algorithm that finds the occurrences of a pattern string in a text string. It is a linear-time algorithm, meaning that its running time is proportional to the length of the text string.
The KMP algorithm works by first building a table of prefixes of the pattern string. This table is used to speed up the search for the pattern in the text string. When a mismatch occurs, the algorithm can use the table to skip over some of the characters in the text string, which reduces the number of comparisons that need to be made.
The KMP algorithm is one of the most efficient string-matching algorithms. It is often used in text editors, search engines, and other applications that need to find patterns in strings.
### C++ Implementation
The following is a C++ implementation of the KMP algorithm:
```c++
#include <iostream>
#include <string>
using namespace std;
// This function builds a table of prefixes of the pattern string.
// The table is used to speed up the search for the pattern in the text string.
void build_prefix_table(const string& pattern, int* table) {
int n = pattern.length();
// Initialize the table to all zeros.
for (int i = 0; i < n; i++) {
table = 0;
}
// Populate the table.
for (int i = 1; i < n; i++) {
int j = table[i - 1];
while (j > 0 && pattern != pattern[j]) {
j = table[j - 1];
}
if (pattern == pattern[j]) {
table = j + 1;
}
}
}
// This function finds the occurrences of the pattern string in the text string.
// The function returns a vector of the starting positions of the occurrences in the text string.
vector<int> find_all_occurrences(const string& pattern, const string& text) {
int n = pattern.length();
int m = text.length();
// Build the prefix table for the pattern string.
int* table = new int[n];
build_prefix_table(pattern, table);
// Initialize the results vector.
vector<int> results;
// Search for the pattern in the text string.
int i = 0;
int j = 0;
while (i < m) {
while (j > 0 && text != pattern[j]) {
j = table[j - 1];
}
if (text == pattern[j]) {
j++;
}
if (j == n) {
// We have found an occurrence of the pattern.
results.push_back(i - n + 1);
j = table[j - 1];
}
i++;
}
// Delete the prefix table.
delete[] table;
// Return the results vector.
return results;
}
int main() {
// The pattern string.
string pattern = "abcab";
// The text string.
string text = "abababcabab";
// Find all occurrences of the pattern in the text string.
vector<int> results = find_all_occurrences(pattern, text);
// Print the results.
for (int i = 0; i < results.size(); i++) {
cout << results << endl;
}
return 0;
}
```
### References
* [The Knuth-Morris-Pratt
Thuật toán Knuth-Morris-Pratt (KMP) là một thuật toán phù hợp với chuỗi tìm thấy sự xuất hiện của chuỗi mẫu trong chuỗi văn bản.Nó là một thuật toán thời gian tuyến tính, có nghĩa là thời gian chạy của nó tỷ lệ thuận với độ dài của chuỗi văn bản.
Thuật toán KMP hoạt động bằng cách đầu tiên xây dựng một bảng tiền tố của chuỗi mẫu.Bảng này được sử dụng để tăng tốc tìm kiếm mẫu trong chuỗi văn bản.Khi xảy ra sự không phù hợp, thuật toán có thể sử dụng bảng để bỏ qua một số ký tự trong chuỗi văn bản, giúp giảm số lượng so sánh cần được thực hiện.
Thuật toán KMP là một trong những thuật toán phù hợp với chuỗi hiệu quả nhất.Nó thường được sử dụng trong các trình soạn thảo văn bản, công cụ tìm kiếm và các ứng dụng khác cần tìm các mẫu trong chuỗi.
### C ++ triển khai
Sau đây là triển khai C ++ của thuật toán KMP:
`` `C ++
#include <Istream>
#include <String>
sử dụng không gian tên STD;
// Hàm này xây dựng một bảng tiền tố của chuỗi mẫu.
// Bảng được sử dụng để tăng tốc tìm kiếm mẫu trong chuỗi văn bản.
void build_prefix_table (const String & mẫu, int* bảng) {
int n = mẫu.length ();
// Khởi tạo bảng vào tất cả các số không.
for (int i = 0; i <n; i ++) {
Bảng = 0;
}
// Duy trì bảng.
for (int i = 1; i <n; i ++) {
int j = bảng [i - 1];
while (j> 0 && mẫu ! = mẫu [j]) {
J = Bảng [J - 1];
}
if (mẫu == mẫu [j]) {
Bảng = j + 1;
}
}
}
// Hàm này tìm thấy sự xuất hiện của chuỗi mẫu trong chuỗi văn bản.
// Hàm trả về một vectơ của các vị trí bắt đầu của các lần xuất hiện trong chuỗi văn bản.
Vector <Int> find_all_occurences (const String & mẫu, chuỗi const & text) {
int n = mẫu.length ();
int m = text.length ();
// Xây dựng bảng tiền tố cho chuỗi mẫu.
int* bảng = new int [n];
build_prefix_table (mẫu, bảng);
// Khởi tạo vectơ kết quả.
Kết quả vector <Int>;
// Tìm kiếm mẫu trong chuỗi văn bản.
int i = 0;
int j = 0;
while (i <m) {
while (j> 0 && text ! = mẫu [j]) {
J = Bảng [J - 1];
}
if (text == mẫu [j]) {
J ++;
}
if (j == n) {
// Chúng tôi đã tìm thấy một sự xuất hiện của mẫu.
kết quả.push_back (i - n + 1);
J = Bảng [J - 1];
}
i ++;
}
// Xóa bảng tiền tố.
xóa [] bảng;
// Trả về vectơ kết quả.
Kết quả trả lại;
}
int main () {
// Chuỗi mẫu.
chuỗi mẫu = "abcab";
// chuỗi văn bản.
Chuỗi văn bản = "Abababcabab";
// Tìm tất cả các lần xuất hiện của mẫu trong chuỗi văn bản.
Vector <Int> results = find_all_occurences (mẫu, văn bản);
// In kết quả.
for (int i = 0; i <results.size (); i ++) {
cout << kết quả << endl;
}
trả lại 0;
}
`` `
### Người giới thiệu
* [Knuth-Morris-Pratt
=======================================
KMP algorithm ## KMP Algorithm in C++
The Knuth-Morris-Pratt (KMP) algorithm is a string-matching algorithm that finds the occurrences of a pattern string in a text string. It is a linear-time algorithm, meaning that its running time is proportional to the length of the text string.
The KMP algorithm works by first building a table of prefixes of the pattern string. This table is used to speed up the search for the pattern in the text string. When a mismatch occurs, the algorithm can use the table to skip over some of the characters in the text string, which reduces the number of comparisons that need to be made.
The KMP algorithm is one of the most efficient string-matching algorithms. It is often used in text editors, search engines, and other applications that need to find patterns in strings.
### C++ Implementation
The following is a C++ implementation of the KMP algorithm:
```c++
#include <iostream>
#include <string>
using namespace std;
// This function builds a table of prefixes of the pattern string.
// The table is used to speed up the search for the pattern in the text string.
void build_prefix_table(const string& pattern, int* table) {
int n = pattern.length();
// Initialize the table to all zeros.
for (int i = 0; i < n; i++) {
table = 0;
}
// Populate the table.
for (int i = 1; i < n; i++) {
int j = table[i - 1];
while (j > 0 && pattern != pattern[j]) {
j = table[j - 1];
}
if (pattern == pattern[j]) {
table = j + 1;
}
}
}
// This function finds the occurrences of the pattern string in the text string.
// The function returns a vector of the starting positions of the occurrences in the text string.
vector<int> find_all_occurrences(const string& pattern, const string& text) {
int n = pattern.length();
int m = text.length();
// Build the prefix table for the pattern string.
int* table = new int[n];
build_prefix_table(pattern, table);
// Initialize the results vector.
vector<int> results;
// Search for the pattern in the text string.
int i = 0;
int j = 0;
while (i < m) {
while (j > 0 && text != pattern[j]) {
j = table[j - 1];
}
if (text == pattern[j]) {
j++;
}
if (j == n) {
// We have found an occurrence of the pattern.
results.push_back(i - n + 1);
j = table[j - 1];
}
i++;
}
// Delete the prefix table.
delete[] table;
// Return the results vector.
return results;
}
int main() {
// The pattern string.
string pattern = "abcab";
// The text string.
string text = "abababcabab";
// Find all occurrences of the pattern in the text string.
vector<int> results = find_all_occurrences(pattern, text);
// Print the results.
for (int i = 0; i < results.size(); i++) {
cout << results << endl;
}
return 0;
}
```
### References
* [The Knuth-Morris-Pratt
