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.

Các kiểu dữ liệu trong C ( int - float - double - char ...)
Thuật toán tìm ước chung lớn nhất trong C/C++
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành)
ComboBox - ListBox trong lập trình C# winforms
Random trong Python: Tạo số random ngẫu nhiên
Lệnh cin và cout trong C++
Cách khai báo biến trong PHP, các loại biến thường gặp
Download và cài đặt Vertrigo Server
Thẻ li trong HTML
Thẻ article trong HTML5
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên
Cách dùng thẻ img trong HTML và các thuộc tính của img
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng