Tìm chuỗi con dài nhất không chứa ký tự trùng lặp trong C
Trong lập trình, việc tìm chuỗi con dài nhất không chứa ký tự trùng lặp trong một chuỗi đã cho là một bài toán phổ biến. Trong bài tập này, mình sẽ viết một chương trình trong ngôn ngữ lập trình C để tìm chuỗi con dài nhất có điều kiện không chứa ký tự trùng lặp.
Chương trình tìm chuỗi con dài nhất không chứa ký tự trùng lặp trong C
Phương pháp giải quyết bài lập trình
- Mình sẽ sử dụng kỹ thuật duyệt qua từng ký tự của chuỗi và sử dụng một bộ nhớ đệm để lưu trữ các ký tự đã gặp phải.
- Khi duyệt qua từng ký tự, nếu ký tự đó đã tồn tại trong bộ nhớ đệm, mình sẽ cập nhật độ dài của chuỗi con tạm thời và làm sạch bộ nhớ đệm.
- Sau khi duyệt qua toàn bộ chuỗi, mình sẽ kiểm tra xem chuỗi con tạm thời có lớn hơn chuỗi con dài nhất đã tìm thấy trước đó không.
Hãy xem cách giải như sau:
Dưới đây là một ví dụ về cách cài đặt tìm chuỗi con dài nhất không chứa ký tự trùng lặp trong ngôn ngữ lập trình C:
Bài viết này được đăng tại [free tuts .net]
#include <stdio.h> #include <string.h> // Hàm tìm chuỗi con dài nhất không chứa ký tự trùng lặp void longestUniqueSubstring(char *str) { int maxLength = 0; // Độ dài của chuỗi con dài nhất không chứa ký tự trùng lặp int start = 0; // Vị trí bắt đầu của chuỗi con dài nhất không chứa ký tự trùng lặp int currentLength = 0; // Độ dài của chuỗi con tạm thời int index[256]; // Mảng lưu trữ vị trí xuất hiện gần nhất của các ký tự trong chuỗi // Khởi tạo mảng index với giá trị -1 memset(index, -1, sizeof(index)); for (int i = 0; str[i] != '\0'; i++) { // Lấy vị trí xuất hiện gần nhất của ký tự str[i] int prevIndex = index[str[i]]; // Nếu ký tự str[i] đã xuất hiện trước đó và nằm trong chuỗi con hiện tại if (prevIndex != -1 && prevIndex >= start) { // Cập nhật độ dài của chuỗi con tạm thời và vị trí bắt đầu mới currentLength = i - start; start = prevIndex + 1; } // Cập nhật vị trí xuất hiện gần nhất của ký tự str[i] index[str[i]] = i; // Cập nhật độ dài của chuỗi con tạm thời currentLength++; // Nếu độ dài của chuỗi con tạm thời lớn hơn độ dài của chuỗi con dài nhất đã tìm thấy trước đó if (currentLength > maxLength) { maxLength = currentLength; } } // In chuỗi con dài nhất không chứa ký tự trùng lặp printf("Chuỗi con dài nhất không chứa ký tự trùng lặp: "); for (int i = start; i < start + maxLength; i++) { printf("%c", str[i]); } printf("\n"); } int main() { char str[] = "abcabcbbfreetuts.net"; printf("Chuỗi ban đầu: %s\n", str); longestUniqueSubstring(str); return 0; }
Kết quả
Khi chạy chương trình với chuỗi ban đầu "abcabcbbfreetuts.net", chúng ta sẽ nhận được chuỗi con dài nhất không chứa ký tự trùng lặp là "s.net".
Trong bài tập này, mình đã viết một chương trình trong ngôn ngữ lập trình C để tìm chuỗi con dài nhất không chứa ký tự trùng lặp trong một chuỗi đã cho. Điều này giúp mình hiểu rõ hơn về cách thực hiện các thao tác với chuỗi và làm việc với mảng trong C.