28
4
Một thuật toán chuỗi quan trọng, đây là lần xem xét thứ ba.
Tóm lại, tôi nghĩ sở dĩ một thuật toán nào đó luôn quên là do não không bao giờ nhận ra logic của thuật toán này (tức là mạch não).
Bài viết này chủ yếu giải thích các kịch bản ứng dụng KMP, kiến thức về thuật toán và các ví dụ.
Có hai chuỗi \(A, B\). Tìm số lần \(A\) xuất hiện trong \(B\). Phạm vi: Độ dài chuỗi là \(\leq 1e6 + 10\).
Thực chất, nói một cách đơn giản, KMP tối ưu hóa vòng lặp kép để giải quyết vấn đề khớp chuỗi.
Vì vậy, để tổng hợp lại, nếu bạn gặp phải vấn đề về chuỗi, nếu không thể sử dụng dp, hãy xem xét băm và KMP.
Về mặt toán học, chúng ta đi từ đặc biệt đến chung, vậy nên ở đây chúng ta đi từ bạo lực đến tối ưu hóa.
Lấy \(A = abab, B = abababaaabb\) làm ví dụ. Cách tiếp cận chung là vòng lặp kép và độ phức tạp về thời gian là \(O(n ^ 2)\).
Hãy xem cách thực hiện cụ thể điều này.
Mỗi lần một điểm ban đầu được liệt kê, và sau đó từng điểm một được đánh giá xem chúng có giống nhau hay không. Nếu chúng giống nhau, tiếp tục đánh giá cho đến khi; nếu chúng khác nhau, thoát ra và chọn điểm tiếp theo làm điểm ban đầu.
Trước hết, nếu xét thấy có gì đó không ổn ở vị trí \(k\)thì không phải là hoàn toàn không thể khắc phục được. Nếu tiền tố và hậu tố của chuỗi con này từ \(1 .. k - 1\) không giống nhau, chẳng hạn như \(abcfd\), thì các bit được đánh giá không cần phải đánh giá lại vì chúng đã được di chuyển trở lại Tất cả đều bị so le nên chúng ta tiếp tục lùi lại để xác định xem điểm bắt đầu có giống nhau hay không. Nếu chúng giống nhau, hãy bắt đầu đánh giá từng điểm một. Nếu là loại \(abcabc\) thì sẽ dễ dàng xử lý vì chúng ta có thể thực hiện các thao tác sau.
Trung tâm cá nhân
Điều phát hành
từ bỏ
abcabcbdde abcabcd
Lúc này người thứ bảy phát hiện có vấn đề, có nên bỏ qua không? Tất nhiên là không.
abc|abcbdde |abcabcd
Chỉ cần bắt đầu lại với cùng một tiền tố. Nhưng rõ ràng nó vẫn không khớp trong trường hợp này.
đối với (int i = 1, j = 0; i <= m; i ++ ) { trong khi (j && b[i] != a[j + 1]) j = ne[j]; nếu (b[i] == a[j + 1]) j ++ ; nếu (j == n) { cout << i - n << ' '; j = ne[j]; } }
Thông qua ý tưởng này, bạn chỉ cần duyệt qua chuỗi gốc mỗi lần và độ phức tạp về thời gian là \(O(n)\).
Trước khi so khớp, cần tính toán tiền tố và hậu tố dài nhất tương ứng với từng chữ số trong chuỗi con và ghi lại chữ số cuối cùng của tiền tố.
đối với (int i = 2, j = 0; i <= n; i ++ ) { trong khi (j && a[i] != a[j + 1]) j = ne[j]; nếu (a[i] == a[j + 1]) j ++ ; ne[i] = j; }
xe đạp.
Bằng cách sử dụng các thuộc tính của mảng ne, bạn có thể ngay lập tức nhận được tiền tố và hậu tố giống hệt nhau dài nhất của một chuỗi. Quan sát cho thấy có những chuỗi có phần vòng lặp:
Cái này tôi tự soạn thảo nên sẽ không nói nhiều nữa.
mã số.
Cuối cùng, bài viết về ghi chú: Đánh giá KMP kết thúc tại đây. Nếu bạn muốn biết thêm về ghi chú: Đánh giá KMP, vui lòng tìm kiếm các bài viết của CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .
28
4
0
Vai trò của OkHttp OkHttp là một máy khách HTTP. Nếu muốn lấy dữ liệu qua HTTP, chúng ta cần nhập URL vào trang. Nếu URL không có vấn đề gì thì có thể trả về chuỗi String tương ứng.
Bản ghi là một thuật toán chuỗi quan trọng. Đây là lần xem xét thứ ba. Tóm lại, tôi nghĩ sở dĩ một thuật toán nào đó luôn quên là do não không bao giờ nhận ra logic của thuật toán này (tức là mạch não). Bài viết này chủ yếu giải thích các kịch bản ứng dụng của KMP.
Khái niệm cơ bản về SQL SQL [Vui lòng sửa cho tôi nếu có bất kỳ câu hỏi nào trong bài viết này] Nếu có tiếng vang, các bước cơ bản thông thường là 1. Xác định xem loại chèn là số hay ký tự số [Ví dụ]:
Tag: #Prompt #LLM Thời gian sáng tạo: 2023-04-28 17:05:45 Link: Course (bao gồm JupyterNotebook), phiên bản tiếng Trung Giảng viên: An
Swift là ngôn ngữ lập trình mới dành cho lập trình ứng dụng iOS và OS X. Nó dựa trên C và Objective-C, nhưng không có một số hạn chế về khả năng tương thích của C. Swift áp dụng các mô hình lập trình an toàn và bổ sung các tính năng hiện đại để giúp việc lập trình trở nên dễ dàng hơn, linh hoạt hơn và thú vị hơn. Giao diện dựa trên
VulnStack-Red Sun Target Machine 7 Tổng quan VulnStack7 là môi trường mạng ba lớp bao gồm 5 máy mục tiêu, đó là vùng DMZ, mạng lớp thứ hai và mạng lớp thứ ba. Có nhiều điểm kiến thức liên quan, bao gồm cả việc sử dụng trái phép redis.
Máy mục tiêu Red Sun (1) Lưu ý Tổng quan Máy mục tiêu thâm nhập tên miền có thể thực hành một số kiến thức về thâm nhập tên miền Điều chính là phải làm quen với cú pháp powershell thường mạnh hơn dòng lệnh cmd và nhiều tập lệnh để thâm nhập mã nguồn mở. là PO
Phân tích chi tiết về tám lĩnh vực hoạt động chính 18.1 Lĩnh vực hoạt động của các bên liên quan có liên quan đến tất cả các hoạt động liên quan đến các bên liên quan 1. Mục tiêu mong đợi ① Thiết lập mối quan hệ làm việc hiệu quả với các bên liên quan ② Các bên liên quan xác định mục tiêu của dự án ③ Hỗ trợ sự cải thiện của các bên liên quan trong dự án.
18.3 Phương pháp phát triển và lĩnh vực hiệu suất vòng đời liên quan đến các hoạt động và chức năng liên quan đến phương pháp phát triển, nhịp độ phân phối dự án và vòng đời 1. Mục tiêu mong đợi: ① Phương pháp phát triển phù hợp với các sản phẩm bàn giao của dự án; giá trị của các bên liên quan
18.7 Lĩnh vực Hiệu suất Đo lường Lĩnh vực Hiệu suất Đo lường bao gồm các hoạt động và chức năng liên quan đến đánh giá hiệu suất dự án và đưa ra các phản hồi thích hợp Đo lường là quá trình đánh giá hiệu suất dự án và thực hiện các hành động ứng phó phù hợp để duy trì hiệu suất dự án tối ưu. 1. Mục tiêu dự kiến: ① Tình trạng dự án
cài đặt pygraphviz, hệ thống windows: Tư thế cài đặt đúng: Prebuild-Binaries/PyGraphviz at master · CristiFati/Prebuild-Binar
Hôm nay tôi sẽ giới thiệu với các bạn cách cấu hình công cụ tải lại nóng devtools trong các công cụ phát triển IDEA. 1. Giới thiệu nguyên lý của devtools spring-boot-devtools là hot loading do spring cung cấp cho các nhà phát triển.
1. Biểu thức chính quy là gì // Biểu thức chính quy (biểu thức chính quy) là một đối tượng mô tả một mẫu ký tự; // JS định nghĩa lớp RegExp để biểu diễn các biểu thức chính quy // Cả String và RegExp đều xác định cách sử dụng;
Hiện tại là 2022-04-25 23:48:03. Người ta ước tính rằng bài đăng trên blog này sẽ được chia sẻ trên Internet 1-2 tháng sau. Phiên bản mới nhất của OpenCV3 tại thời điểm này là 3.4.16. gcc, g++, cmake Tất cả đều cần được cài đặt. Không được cài đặt đúng cách,
1. Tổng quan 1. Flink là gì? Apache Flink là một khung và công cụ xử lý phân tán dành cho máy tính có trạng thái
1. Tổng quan về window Flink là một công cụ tính toán thường xử lý các tập dữ liệu phát trực tuyến và vô hạn. Window là một cách để cắt các tập dữ liệu phát trực tuyến vô hạn thành các tập dữ liệu giới hạn để tính toán. Cửa sổ cửa sổ cực kỳ quan trọng trong Flink. 2. Loại cửa sổ w
1. Trigger (Trigger) 1.1. Trường hợp 1 sử dụng Global window + trigger để đếm các từ xuất hiện ba lần (hơi giống CountWindow).
1. Ngữ nghĩa thời gian liên quan đến ba khái niệm thời gian quan trọng trong Flink: EventTime, IngestionTime và TreatmentTime. 1.1 EventTime EventTime thể hiện các sự kiện nhật ký
1. Tổng quan Lấy số từ làm ví dụ, tại sao flink có thể đếm tổng số mỗi từ mỗi lần nhập dữ liệu? Chúng tôi chưa hiển thị giá trị trạng thái của từng từ đã lưu nhưng với mỗi phần dữ liệu có thể tính được tổng số từ. Trên thực tế, Flink duy trì mọi
1. Tổng quan Cơ chế điểm kiểm tra là nền tảng cho độ tin cậy của Flink. Nó có thể đảm bảo rằng khi người vận hành bị lỗi do một số lý do (chẳng hạn như thoát bất thường), cụm Flink có thể khôi phục trạng thái của toàn bộ biểu đồ luồng ứng dụng về trạng thái nhất định trước đó. sự thất bại, đảm bảo rằng biểu đồ luồng ứng dụng là
Tôi là một lập trình viên xuất sắc, rất giỏi!