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