Tìm một chuỗi con trong một chuỗi có sẵn là bài toán thường gặp. Hầu hết các ngôn ngữ lập trình đều cung cấp hàm này. Tuy nhiên, nếu bạn nhận được yêu cầu viết chương trình để thực hiện điều này thì bạn sẽ làm thế nào. Bài dưới đây sẽ nói về điều đó.
Yêu cầu
Viết chương trình khởi tạo một chuỗi, sau đó nhập một chuỗi mới và kiểm tra xem chuỗi mới có xuất hiện trong chuỗi đã có trước đó hay không?
Phân tích và tìm cách giải
- Đầu vào: s=”thanh pho da nang”, Chuỗi mới s1={nang}
- Đầu ra: In ra thông báo chuỗi s1 có xuất hiện trong chuỗi s hay không?
- Phân tích:
– Bạn cần lấy chữ đầu tiên của chuỗi s1 để so sánh với các ký tự của s.
– Nếu không có ký tự nào khớp bạn sẽ thông báo ngay s1 xuất hiện trong s.
– Nếu có ký tự khớp bạn so sánh hết các ký tự của chuổi s1 và các ký tự của chuỗi s tương ứng từ vị trí khớp.
+ Nếu khớp hoàn toàn bạn thông báo đã tìm thấy
+ Nếu không khớp hoàn toàn bạn quay lại vòng lặp chính để thực hiện cho đến vị trí k=s.length-s1.length
Cách biểu diễn thuật toán
Trong trường hợp này, tôi sử dụng ngôn ngữ giả.
Declare String s="thanh pho da nang", s1
Boolean found=false
Int i,j
Input s1
If s1.lenght >s.length
Print "Chuoi can tim phai ngan hon chuoi chua no"
Exit
Else {
Loop i from 0 to s.length – s1.lenght
If(s[i]=s1[0]) then {
found=true
Loop j from 1 to s1.length-1 {
if s[i+j]<>s[j] then
found=false
break //Thoát khỏi vòng lặp j
}
if found then break //thoát khỏi vòng lặp I vì đã tìm thấy
}
If found
Print s1 + ‘ chua trong chuoi ’ + s
Else
Print s1 + ‘ khong co trong chuoi ’ + s
}
