Bài 11.918 phút đọc

strstr

Sau bài này bạn sẽ làm được

Dùng strstr để tìm chuỗi con
Đếm số lần xuất hiện có và không chồng lấn
Viết hàm thay thế mọi lần xuất hiện của một chuỗi con
Hiểu vì sao thuật toán ngây thơ là O(n nhân m)

Tìm chuỗi con là bài toán nền tảng của mọi trình soạn thảo, mọi công cụ tìm kiếm, mọi bộ lọc văn bản. Thư viện chuẩn cho bạn một hàm làm việc đó, và bài này chỉ ra cách dùng nó để giải những bài toán thật, cùng giới hạn của nó.

#Cách dùng

#include <string.h>

char *strstr(const char *lon, const char *nho);

Tìm lần xuất hiện đầu tiên của chuỗi nho trong chuỗi lon. Trả về con trỏ tới vị trí bắt đầu, hoặc NULL nếu không tìm thấy.

strstr.c

#include <stdio.h>
#include <string.h>

int main(void)
{
    const char *s = "xin chao the gioi";

    char *p = strstr(s, "chao");

    if (p != NULL)
        printf("tim thay tai chi so %td: [%s]\n", p - s, p);

    if (strstr(s, "tam biet") == NULL)
        printf("khong tim thay\n");

    printf("%td\n", strstr(s, "") - s);   /* 0, chuỗi rỗng luôn khớp ở đầu */

    return 0;
}

terminal

./strstr

tim thay tai chi so 4: [chao the gioi]
khong tim thay
0

Chuỗi rỗng luôn tìm thấy ở vị trí đầu

Chuẩn C quy định strstr(s, "") trả về chính s. Điều này hợp lý về mặt toán học nhưng dễ gây vòng lặp vô hạn nếu bạn tìm lặp lại mà không kiểm tra.

/* Vòng lặp vô hạn nếu nho là chuỗi rỗng */
const char *p = s;

while ((p = strstr(p, nho)) != NULL) {
    ++dem;
    p += strlen(nho);        /* cộng 0, p không tiến, lặp mãi */
}

/* Cách chữa: kiểm tra ngay đầu hàm */
if (nho[0] == '\0') return 0;

Kiểm tra chuỗi có chứa chuỗi con hay không

if (strstr(dong, "ERROR") != NULL)
    xu_ly_loi(dong);

/* Gói lại cho dễ đọc */
static int co_chua(const char *lon, const char *nho)
{
    return strstr(lon, nho) != NULL;
}

#Đếm số lần xuất hiện

Có hai định nghĩa khác nhau, và bạn phải chọn một cách rõ ràng: đếm cả những lần chồng lấn, hay chỉ đếm những lần không chồng lấn.

dem.c

/* Đếm KHÔNG chồng lấn: sau mỗi lần khớp, nhảy qua cả chuỗi con. */
size_t dem_khong_chong(const char *lon, const char *nho)
{
    size_t len = strlen(nho);

    if (len == 0) return 0;

    size_t n = 0;
    const char *p = lon;

    while ((p = strstr(p, nho)) != NULL) {
        ++n;
        p += len;
    }

    return n;
}

/* Đếm CÓ chồng lấn: sau mỗi lần khớp, chỉ tiến đúng một ký tự. */
size_t dem_co_chong(const char *lon, const char *nho)
{
    if (nho[0] == '\0') return 0;

    size_t n = 0;
    const char *p = lon;

    while ((p = strstr(p, nho)) != NULL) {
        ++n;
        ++p;
    }

    return n;
}

Chuỗi lớn	Chuỗi con	Không chồng lấn	Có chồng lấn
"aaaa"	"aa"	2	3
"ababab"	"abab"	1	2
"hello"	"l"	2	2
"aaa"	"aaaa"	0	0

#Thay thế mọi lần xuất hiện

Đây là bài toán tổng hợp mọi thứ đã học trong Chương 11: tìm kiếm, sao chép, nối, và quản lý kích thước bộ đệm.

thay-the.c

#include <stdio.h>
#include <string.h>

/* Thay mọi lần xuất hiện của cu bằng moi, ghi kết quả vào ra.
   Trả về độ dài kết quả đáng lẽ cần, giống quy ước của snprintf.
   Nếu giá trị trả về lớn hơn hoặc bằng co thì kết quả đã bị cắt. */
size_t thay_the(char *ra, size_t co, const char *nguon,
                const char *cu, const char *moi)
{
    size_t len_cu  = strlen(cu);
    size_t len_moi = strlen(moi);
    size_t ghi = 0;

    if (len_cu == 0) {
        /* Không có gì để thay, chỉ sao chép */
        size_t n = strlen(nguon);

        if (co > 0) {
            size_t chep = n < co - 1 ? n : co - 1;

            memcpy(ra, nguon, chep);
            ra[chep] = '\0';
        }

        return n;
    }

    const char *p = nguon;

    for (;;) {
        const char *tim = strstr(p, cu);
        size_t doan = tim != NULL ? (size_t)(tim - p) : strlen(p);

        /* Chép đoạn văn bản trước chỗ khớp */
        for (size_t i = 0; i < doan; ++i) {
            if (ghi + 1 < co) ra[ghi] = p[i];
            ++ghi;
        }

        if (tim == NULL) break;

        /* Chép chuỗi thay thế */
        for (size_t i = 0; i < len_moi; ++i) {
            if (ghi + 1 < co) ra[ghi] = moi[i];
            ++ghi;
        }

        p = tim + len_cu;
    }

    if (co > 0)
        ra[ghi < co ? ghi : co - 1] = '\0';

    return ghi;
}

dung.c

int main(void)
{
    char ra[128];

    size_t n = thay_the(ra, sizeof ra,
                        "con meo ngoi tren con meo khac",
                        "meo", "cho");

    printf("[%s]\n", ra);
    printf("can %zu ky tu\n", n);

    if (n >= sizeof ra)
        fprintf(stderr, "Ket qua bi cat\n");

    return 0;
}

terminal

./dung

[con cho ngoi tren con cho khac]
can 30 ky tu

Vì sao không thay thế tại chỗ

/* Nếu chuỗi thay thế DÀI HƠN chuỗi cũ, kết quả dài hơn nguồn.
   Thay tại chỗ sẽ đè lên phần chưa xử lý. */
thay_the(s, sizeof s, s, "a", "aaaa");   /* SAI */

Chỉ khi chuỗi mới ngắn hơn hoặc bằng chuỗi cũ thì thay tại chỗ mới an toàn, và ngay cả khi đó bạn vẫn phải viết cẩn thận với hai chỉ số đọc và ghi như mẫu ở Bài 9.4.

#Độ phức tạp thuật toán ngây thơ

Thuật toán đơn giản nhất: với mỗi vị trí trong chuỗi lớn, thử so khớp toàn bộ chuỗi con.

for (mỗi vị trí i trong chuỗi lớn)
    for (mỗi ký tự j của chuỗi con)
        nếu khác nhau thì bỏ vị trí i, sang vị trí tiếp theo

Trường hợp	Số phép so sánh	Ví dụ
Thông thường	gần bằng n	Văn bản tiếng Việt, hầu hết vị trí sai ngay ký tự đầu
Xấu nhất	n nhân m	Chuỗi lớn là aaaa...a, chuỗi con là aaa...ab

terminal

# Chuỗi lớn 1 triệu ký tự 'a', chuỗi con 1000 ký tự 'a' rồi 'b'

./do-strstr

ngay tho tu cai : 0.412 s
strstr cua glibc: 0.004 s

#Tự cài lại

my-strstr.c

char *my_strstr(const char *lon, const char *nho)
{
    if (nho[0] == '\0')
        return (char *)lon;        /* chuỗi rỗng khớp ngay ở đầu */

    for (; *lon != '\0'; ++lon) {
        const char *a = lon;
        const char *b = nho;

        while (*a == *b && *b != '\0') {
            ++a;
            ++b;
        }

        if (*b == '\0')
            return (char *)lon;    /* đã so hết chuỗi con, khớp toàn bộ */
    }

    return NULL;
}

test.c

#include <assert.h>
#include <string.h>

static void kt(const char *lon, const char *nho)
{
    assert(my_strstr(lon, nho) == strstr(lon, nho));
}

int main(void)
{
    kt("hello world", "world");    /* khớp ở giữa */
    kt("hello world", "hello");    /* khớp ở đầu */
    kt("hello world", "d");        /* khớp ở cuối */
    kt("hello world", "xyz");      /* không khớp */
    kt("hello", "hello world");    /* chuỗi con dài hơn */
    kt("hello", "");               /* chuỗi con rỗng */
    kt("", "abc");                 /* chuỗi lớn rỗng */
    kt("", "");                    /* cả hai rỗng */
    kt("aaaa", "aa");              /* nhiều lần khớp chồng lấn */
    kt("abcabcabd", "abcabd");     /* khớp một phần rồi phải quay lại */

    puts("Tat ca kiem thu deu qua");

    return 0;
}

Tự làm thử

Dùng strstr tìm một từ trong câu, in cả con trỏ lẫn chỉ số tìm thấy.
Cài cả hai hàm đếm, kiểm chứng bằng bảng bốn dòng trong bài.
Viết vòng lặp tìm lặp lại mà quên kiểm tra chuỗi con rỗng, quan sát vòng lặp vô hạn.
Cài hàm thay_the đầy đủ, thử với chuỗi mới dài hơn, ngắn hơn và bằng chuỗi cũ.
Đo thời gian của my_strstr và strstr với trường hợp xấu nhất mô tả trong bài.
Cài my_strstr và chạy đủ mười trường hợp kiểm thử, so con trỏ với bản chuẩn.
Viết công cụ lọc dòng chứa một từ khóa, giống lệnh grep đơn giản.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

strstr trả về con trỏ tới lần xuất hiện đầu tiên, hoặc NULL. Chuỗi rỗng luôn khớp ngay ở đầu.
Tìm lặp lại phải kiểm tra chuỗi con rỗng, nếu không vòng lặp chạy vô hạn.
Đếm có chồng lấn và không chồng lấn cho kết quả khác nhau, phải chọn và ghi rõ một định nghĩa.
Hàm ghi vào bộ đệm người gọi nên theo mẫu của snprintf: luôn đếm, chỉ ghi khi còn chỗ, trả về độ dài đáng lẽ cần.
Thuật toán ngây thơ là n nhân m ở trường hợp xấu nhất, còn bản thư viện là tuyến tính.