SIMPLE
STRING
ARRAY
SORTING
POINTER
CALCULATION
NUMBER
OTHER
C
BÀI TẬP C
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

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.

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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".

Screenshot 202024 03 16 20230853 png

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ùng chuyên mục:

Các hàm xử lý ngày tháng (datetime.h) trong C/C++

Các hàm xử lý ngày tháng (datetime.h) trong C/C++

Các hàm xử lý số thực (float.h) trong C/C++

Các hàm xử lý số thực (float.h) trong C/C++

Các hàm xử lý số nguyên lớn (bigint.h) trong C/C++

Các hàm xử lý số nguyên lớn (bigint.h) trong C/C++

Các hàm xử lý thời gian (time.h) trong C

Các hàm xử lý thời gian (time.h) trong C

Các hàm xử lý chuỗi (string.h) trong C/C++

Các hàm xử lý chuỗi (string.h) trong C/C++

Thread Pools và Parallel Algorithms trong C++

Thread Pools và Parallel Algorithms trong C++

Tạo và quản lý các Multithreading trong C++

Tạo và quản lý các Multithreading trong C++

Xử lý ngoại lệ khi làm việc với Memory Allocation trong C++

Xử lý ngoại lệ khi làm việc với Memory Allocation trong C++

Try, Catch, và Throw của Exception Handling trong C++

Try, Catch, và Throw của Exception Handling trong C++

Cách sử dụng Lambda Expressions trong C++

Cách sử dụng Lambda Expressions trong C++

Sử dụng weak_ptr trong C++

Sử dụng weak_ptr trong C++

Sử dụng shared_ptr trong C++

Sử dụng shared_ptr trong C++

Sử dụng unique_ptr trong C++

Sử dụng unique_ptr trong C++

Tổng quan về Smart Pointers trong C++

Tổng quan về Smart Pointers trong C++

Sử dụng Iterators trong STL của C++

Sử dụng Iterators trong STL của C++

[Iterator] Sử dụng Vector trong C++

[Iterator] Sử dụng Vector trong C++

[Iterator] Sử dụng trong List trong C++

[Iterator] Sử dụng trong List trong C++

[STL] Sử dụng Vector trong C++

[STL] Sử dụng Vector trong C++

Tổng quan về Iterators trong C++

Tổng quan về Iterators trong C++

[STL] Các hàm thường dùng của lớp Vector trong C++

[STL] Các hàm thường dùng của lớp Vector trong C++

Top