Vấn đề khớp chuỗi

Cho một chuỗi s và một chuỗi mẫu p để khớp. Chuỗi mẫu p có thể xuất hiện nhiều lần trong s và vị trí bắt đầu của tất cả các lần xuất hiện của chuỗi mẫu p trong s đều được yêu cầu.

Thuật toán đối sánh vũ phu BF

Ý tưởng thuật toán

Khi gặp vấn đề về khớp chuỗi, người ta dễ dàng nghĩ đến các giải pháp mạnh mẽ. Ý tưởng của thuật toán Brute Force để so khớp chuỗi rất đơn giản, đó là liệt kê điểm bắt đầu i trong s và khớp chuỗi p cho mỗi điểm bắt đầu. Các bước chung là: (1) Liệt kê điểm i, xác định giá trị trạng thái flag = true và k = i, j = 0; (2) Nếu s[k] == p[j], tiếp tục k++, j++; [k] != p[j], đặt cờ thành false và ngắt; (3) Đối với mỗi điểm bắt đầu i, nếu flag = true, xuất ra vị trí i.

Mã thuật toán Brute Force

Chỉ số dưới của chuỗi đầu vào ở đây bắt đầu từ 1, phù hợp với văn bản sau.

                        
                          #include #include sử dụng không gian tên std; static const int N = 1000010, M = 100010; char s[N], p[M]; int slen, plen; int ne[N]; int main(){ cin >> plen >> p + 1 >> slen >> s + 1; for(int i = 1; i <= slen - plen + 1; i++){ bool flag = true; for(int j = 1, k = i; j <= plen; j++, k++){ if(s[k] != p[j]){ flag = false; break; } } if(flag) printf("%d ", i); } }

                        
                      

---

Thuật toán KMP

Ý nghĩa của thuật toán KMP

Thuật toán KMP là thuật toán so khớp chuỗi cải tiến do DEKnuth, JHMorris và VRpratt đề xuất nên còn được gọi là thuật toán KMP. Cốt lõi của thuật toán của nó là sử dụng thông tin được ghi trong mảng tiếp theo để giảm số lượng khớp ở một mức độ nhất định sau khi khớp chuỗi không thành công, từ đó nâng cao hiệu quả của việc khớp chuỗi.

Các khái niệm cơ bản liên quan đến thuật toán KMP

(1) s là một chuỗi mẫu; (2) p là một chuỗi mẫu, nghĩa là chuỗi cần khớp trong s; (3) Các hậu tố phổ biến: Giả sử rằng độ dài của một chuỗi là len và chỉ số dưới bắt đầu từ 1, nếu phạm vi [1, i] và phạm vi [j, len] trong chuỗi hoàn toàn khớp nhau thì hai đoạn này được gọi là tiền tố và hậu tố chung của chuỗi (4) mảng tiếp theo: Mảng tiếp theo; là cốt lõi của thuật toán KMP, next[i ] Những gì được ghi lại là chuỗi mẫu p Độ dài hậu tố chung dài nhất trong phạm vi độ dài của tiền tố i, sẽ được giải thích chi tiết sau. Nếu xảy ra sự không khớp khi thuật toán KMP thực hiện khớp chuỗi, thì chuỗi mẫu p có thể được dịch chuyển trở lại tương đương dựa trên thông tin được ghi trong mảng tiếp theo. (5) Hai bước cốt lõi: 1. Giải mảng tiếp theo 2. Thực hiện so khớp chuỗi. Lưu ý rằng chỉ số dưới của chuỗi bắt đầu từ 1 và so sánh s[i] và p[i + 1] mỗi lần trong quá trình so khớp. .

Ý tưởng phù hợp của thuật toán KMP

Sơ đồ lõi khớp thuật toán KMP

Phạm vi được đánh dấu bằng đường chấm màu đỏ là phần hiện khớp và vòng tròn rỗng màu đỏ là hai ký tự hiện đang được so sánh.

Ví dụ và minh họa khớp thuật toán KMP

（1）

（2）

（3）

（4）

（5）

（6）

（7）

Tại thời điểm này, có sự không khớp và j = next[j] cần được đặt.

（8）

Dễ dàng nhận thấy độ dài hậu tố chung dài nhất của 6 độ dài đầu tiên trong p là 2, j = next[6] = 2.

（9）

Nó tương đương với việc di chuyển toàn bộ chuỗi mẫu p sang phải theo độ dài của chuỗi j trước đó - next[j] và sau đó bắt đầu khớp.

（10）

Tại thời điểm này, lại có sự không khớp và j = next[j] cần được thay đổi.

（11）

Độ dài hậu tố chung dài nhất của 2 độ dài đầu tiên trong chuỗi mẫu p là 0, j = next[2] = 0 *.

（12）

Nó tương đương với việc di chuyển toàn bộ chuỗi mẫu p sang phải theo độ dài của chuỗi j trước đó - next[j] và sau đó bắt đầu khớp.

（13）

Bắt đầu từ ký tự hiện tại s[i], chuỗi mẫu p được khớp thành công. (Một số đã bị bỏ qua trước đó).

Thuật toán KMP khớp với mã lõi

                        
                              //Thao tác so khớp for(int i = 1, j = 0; i <= n; i++){ // Sự không khớp có thể vẫn không khớp sau chuyển động tổng thể, vì vậy hãy sử dụng while(j && s[i] != p [ j + 1]) j = ne[j]; //Hai ký tự hiện tại khớp với if(s[i] == p[j + 1]) j++; " , tôi - m + 1); //Trả về vị trí bắt đầu khớp j = ne[j] //Có thể có nhiều vị trí khớp, tiếp tục khớp} }

                        
                      

---

Giải thích chi tiết về mảng tiếp theo

Ý nghĩa và giải pháp của mảng tiếp theo

next[i] ghi lại độ dài của hậu tố chung dài nhất trong phạm vi độ dài của i trước chuỗi mẫu p. Ví dụ, trong chuỗi ABDAB, có thể thấy hậu tố chung dài nhất trong 4 độ dài đầu tiên của chuỗi này là A, thì đối với chuỗi này, next[4] = 1; tương tự, hậu tố chung dài nhất trong 5 chuỗi đầu tiên; Độ dài của chuỗi này là AB, do đó next[5] = 2.

Giải pháp cho mảng tiếp theo rất giống với quy trình so khớp chuỗi ở trên, tương đương với việc so khớp chính bạn. Coi một p là một chuỗi mẫu, coi p còn lại là một chuỗi và khớp nó với chuỗi mẫu p bắt đầu từ chỉ mục 2.

sơ đồ lõi mảng tiếp theo

Phạm vi được đánh dấu bằng đường chấm màu đỏ là phần hiện khớp và vòng tròn rỗng màu đỏ là hai ký tự hiện đang được so sánh.

(1) Giải quyết việc khớp ký tự hiện tại của mảng tiếp theo

(2) Giải quyết vấn đề ký tự hiện tại không khớp ở mảng tiếp theo

ví dụ và minh họa mảng tiếp theo

（1）

（2）

（3）

（4）

Một ký tự trùng khớp xảy ra.

（5）

Một ký tự trùng khớp xảy ra.

（6）

Một ký tự trùng khớp xảy ra.

（7）

Việc giải mảng tiếp theo đã hoàn thành.

mã lõi mảng tiếp theo

                        
                              //Tìm mảng next[] for(int i = 2, j = 0; i <= m; i++){ // Ký tự hiện tại không khớp while(j && p[i] != p[j + 1] ) j = ne[j]; if(p[i] == p[j + 1]) j++; //Ghi lại độ dài hậu tố chung dài nhất trước i ne[i] = j }

                        
                      

Chỉ số chuỗi và lý do tại sao mảng tiếp theo được xác định theo cách này

Các chỉ số dưới của chuỗi ở trên đều bắt đầu từ 1. Không khó để thực hiện C/C++ có thể nhập từ 1. Trong các ngôn ngữ khác như python, trước tiên chỉ cần chèn một ký tự. Chỉ số bắt đầu từ 1 chủ yếu liên quan đến định nghĩa của mảng tiếp theo. Mảng tiếp theo ghi lại độ dài của hậu tố chung dài nhất trong một phạm vi nhất định trong chuỗi mẫu p. Nếu chỉ số dưới bắt đầu từ 0, thì mẫu thuật toán KMP này cũng có thể được thực hiện, nhưng next[0] cần được đặt thành -1, và kết quả Mảng tiếp theo phần nào vi phạm ý nghĩa riêng của nó (nó trở thành bản ghi có độ dài hậu tố chung dài nhất của chỉ số i đầu tiên - 1). Sau đây là mẫu thuật toán KMP với các chỉ số bắt đầu từ 0

                        
                          int main(){ cin >> m >> p >> n >> s; ne[0] = -1; đối với (int i = 1, j = -1; i < m; i ++ ){ khi (j >= 0 && p[j + 1] != p[i]) j = ne[j]; nếu (p[j + 1] == p[i]) j ++ ; ne[i] = j; } đối với (int i = 0, j = -1; i < n; i ++ ){ khi (j != -1 && s[i] != p[j + 1]) j = ne[j]; nếu (s[i] == p[j + 1]) j ++ ; nếu (j == m - 1){ cout << i - j << ' '; j = ne[j]; } } //Phép toán tiếp theo //cout<
                      

Sau đây là kết quả mảng tiếp theo thu được từ mẫu của chỉ số dưới trên bắt đầu từ 0: Có thể thấy giá trị của bản ghi mảng tiếp theo chính xác là độ dài hậu tố chung dài nhất của chỉ số dưới i đầu tiên - 1.

---

chương trình hoàn chỉnh

Mã chương trình hoàn chỉnh

                        
                          #include sử dụng không gian tên std; static const int N = 1000010, M = 100010; char s[N], p[M]; int slen, plen; int ne[N]; int main(){ cin >> plen >> p + 1 >> slen >> s + 1; for(int i = 2, j = 0; i <= plen; i++){ while(j && p[i] != p[j + 1]) j = ne[j]; if(p[i] == p[j + 1]) j++; ne[i] = j; } for(int i = 1, j = 0; i <= slen; i++){ while(j && s[i] != p[j + 1]) j = ne[j]; if(s[i] == p[j + 1]) j++; if(j == plen){ cout<
                      

Chạy thử chương trình

---

phần tái bút

Cách viết hầu hết các KMP trên Internet không giống như trong bài tôi viết này, và định nghĩa mảng tiếp theo cũng khác. Những gì tôi ghi lại là cách viết thuật toán KMP mà tôi nghĩ là dễ hiểu nhất. Tôi không có ý coi thường các cách viết khác. Có lẽ mỗi cách đều có ưu điểm riêng.

Cuối cùng, bài viết về thuật toán KMP [Cấu trúc dữ liệu] (bao gồm giải thích chi tiết về mảng tiếp theo) kết thúc tại đây. Nếu bạn muốn biết thêm về thuật toán KMP [Cấu trúc dữ liệu] (bao gồm giải thích chi tiết về mảng tiếp theo), vui lòng tìm kiếm bài viết CFSDN. Hoặc tiếp tục duyệt các bài viết liên quan, tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .