Bài Toán Chuỗi Con đối Xứng Dài Nhất - TaiLieu.VN

Có thể bạn quan tâm

OPTADS360 intTypePromotion=1 zunia.vn

Tuyển sinh 2024 dành cho Gen-Z zunia.vn

Danh mục
- - Tài Liệu Tham Khảo
    - Kinh Doanh-Marketing
    - Kinh Tế - Quản Lý
    - Tài Chính - Ngân Hàng
    - Công Nghệ Thông Tin
    - Ngoại Ngữ
    - Kỹ Thuật - Công Nghệ
    - Khoa Học Tự Nhiên
    - Khoa Học Xã Hội
    - Văn Hoá - Nghệ Thuật
    - Biểu mẫu - Văn bản
    - Sáng kiến kinh nghiệm
    - Ôn thi ĐH-CĐ
    - Giáo án điện tử
    - Bài giảng điện tử
    - Đề thi - Kiểm tra
    - Bài tập SGK
  - Bộ Tài Liệu 4.0
  - Bộ Sưu Tập
  - Luận Văn & Đề Tài
  - Mẫu Slide Powerpoint
  - Khóa Học Online
  - Tài Liệu Phổ Thông
    - Bài học SGK
    - Giải SGK
    - Soạn văn
    - Văn mẫu
    - Đề Thi
    - Trắc nghiệm Online
  - Học trực tuyến
    - Học Online
    - Đề thi Online
    - Tư liệu
  - Trắc Nghiệm MBTI
  - Trắc Nghiệm Holland

NÂNG CẤP

Đăng Nhập | Đăng Ký Chủ đề »

Ngôn ngữ lập trình
Lập trình hướng đối tượng
Lập trình Android
Lập trình Java
Lập trình IOS

HOT
- FORM.04: Bộ 240+ Biểu Mẫu Chứng Từ Kế...
- LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên...
- CMO.03: Bộ Tài Liệu Hệ Thống Quản Trị...
- FORM.07: Bộ 125+ Biểu Mẫu Báo Cáo...
- CEO.27: Bộ Tài Liệu Dành Cho StartUp...
- FORM.08: Bộ 130+ Biểu Mẫu Thống Kê...
- LV.26: Bộ 320 Luận Văn Thạc Sĩ Y...
- CEO.29: Bộ Tài Liệu Hệ Thống Quản Trị...
- TL.01: Bộ Tiểu Luận Triết Học
CEO.24: Bộ 240+ Tài Liệu Quản Trị Rủi Ro Doanh...

TUYỂN SINH

YOMEDIA ADSENSE Trang Chủ » Công Nghệ Thông Tin » Kỹ thuật lập trình Bài toán chuỗi con đối xứng dài nhất

Chia sẻ: Abcdef_45 Abcdef_45 | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu 1.274 lượt xem 41 download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu. Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước. Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu. Dữ liệu vào Gồm một dòng duy nhất chứa chuỗi S, chỉ gồm những chữ cái in thường. Kết quả Gồm một dòng duy nhất là một chuỗi con đối xứng dài nhất của chuỗi S. Nếu có nhiều kết quả, chỉ...

AMBIENT/ Chủ đề:

Công nghệ thông tin
cấu trúc dữ liệu
lý thuyết đồ thị
Javascript
ASP.NET
Tin học đại cương
giáo trình Tin học đại cương
bài giảng Tin học đại cương
tài liệu Tin học đại cương
lý thuyết Tin học đại cương

Bình luận(0) Đăng nhập để gửi bình luận!

Đăng nhập để gửi bình luận! Lưu

Nội dung Text: Bài toán chuỗi con đối xứng dài nhất

Bài toán chuỗi con đối xứng dài nhất Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu. Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước. Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu. Dữ liệu vào Gồm một dòng duy nhất chứa chuỗi S, chỉ gồm những chữ cái in thường. Kết quả Gồm một dòng duy nhất là một chuỗi con đối xứng dài nhất của chuỗi S. Nếu có nhiều kết quả, chỉ cần in ra một kết quả bất kỳ. Giới hạn Chuỗi S có độ dài không vượt quá 2000. Ví d ụ Dữ liệu vào lmevxeyzl Kết quả level Ta sẽ chuyển bài toán về một bài toán quy hoạch động cơ bản là: Bài toán tìm chuỗi con chung dài nhất Với dữ liệu vào là S1. Ta tạo chuỗi S2 là chuỗi ngược của S1bằng cách chép các phần tử của chuỗi S1 vào chuỗi S2 theo thứ tự ngược lại. Sau đó ta sẽ tìm chuỗi con chung dài nhất của S1 và S2. Ta chỉ cần tìm chuỗi con chung dài nhất của một phần của S1 và nghịch đảo phần còn lại, tức là ta chỉ xét một phần của bảng phương án với i+j
Ta có bảng phương án Khi đó chuỗi con chung dài nhất là le của S14=“lmev” và S24=”lzye” (hoặc S13=”lme” và S25=”lzyex”) Khi ta truy vết để tìm chuỗi con chung ta sẽ kiểm tra xem chuỗi đối xứng của chúng ta là lẻ hay chẵn (số kí tự). Nếu i+j=chiều dài của S1, tức là 2 kí tự đối xứng đứng liên tiếp nhau trong  S1, vì vậy chuỗi đối xứng là chẵn. Ngược lại, tức là mọi i+j
#define Output "doixung.out" char S1[2000],S2[2000],S[2000]; int B[2001][2001],T[2001][2001]; int L,MaxP; void GetInput() { ifstream fi(Input); fi>>S1; fi.close(); L=strlen(S1); for (int i=0; i
T[i][j]=1; } else { B[i][j]=B[i][j-1]; T[i][j]=-1; } } } void Trace() { int maxP=0; int i,j; for (i=1; imaxP) { maxP=B[i][L-i]; j=L-i; } i=L-j; int k=i; int Ls=maxP; bool even=false; while (i>0 && j>0) { if (T[i][j]==0) { if (i+j==L) even=true; S[--Ls]=S1[i-1]; i--; j--; } else if (T[i][j]==1) i--; else j--; } j=maxP-1;
if (!even) S[maxP++]=S1[k]; while (j>=0) S[maxP++]=S[j--]; S[maxP]=0; } int main() { GetInput(); Optimize(); Trace(); PutOutput(); return 0; }

ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

Thêm tài liệu vào bộ sưu tập có sẵn:

Đồng ý Thêm vào bộ sưu tập mới:

*Tên bộ sưu tập Mô Tả: *Từ Khóa: Tạo mới Báo xấu

Hãy cho chúng tôi biết lý do bạn muốn thông báo. Chúng tôi sẽ khắc phục vấn đề này trong thời gian ngắn nhất.
Không hoạt động
Có nội dung khiêu dâm
Có nội dung chính trị, phản động.
Spam
Vi phạm bản quyền.
Nội dung không đúng tiêu đề.

Hoặc bạn có thể nhập những lý do khác vào ô bên dưới (100 ký tự): Vui lòng nhập mã xác nhận vào ô bên dưới. Nếu bạn không đọc được, hãy Chọn mã xác nhận khác.. Đồng ý LAVA AANETWORK THÔNG TIN