[Thuật toán] BÀI TOÁN GETSTRING
[Thuật toán] BÀI TOÁN GETSTRING Tháng Bảy 18, 2013 nguyenvanquan7826 Thuật toán Leave a response Cho xâu S có độ dài không quá 10^5, và tập A có n phần tử(n≤100) gồm các kí tự trong bảng mã ASCII, phân biệt chữ hoa và chữ ...
[Thuật toán] BÀI TOÁN GETSTRING
Cho xâu S có độ dài không quá 10^5, và tập A có n phần tử(n≤100) gồm các kí tự trong bảng mã ASCII, phân biệt chữ hoa và chữ thường. Hãy tìm chuỗi con liên tiếp trong S sao cho chứa đầy đủ các kí tự trong tập A và có độ dài ngắn nhất.
(Chuỗi con liên tiếp là chuỗi có các ký tự theo thứ tự trong A và có thể cách xa nhau)
Dữ liệu vào: file GETSTRING.INP
Dòng đầu ghi chứa xâu S
Dòng thứ 2 là số n.
N dòng tiếp theo, mỗi dòng chứa 1 kí tự trong tập A.
Dữ liệu ra: file GETSTRING.OUT
Gồm 1 dòng duy nhất ghi độ dài chuỗi con ngắn nhất tìm được.
Ví dụ:
GETSTRING.INP
hello the gioi
4
t
e
g
o
GETSTRING.OUT
7
———————
Gọi F[i][j] là khoảng cách từ ký tự A[i] (A[i] = s[j]) đến A[i-1] trong xâu S.
Độ dài chuỗi con cần tìm là khoảng cách ngắn nhất từ A[n] đến A[1].
F[i][j] được tính như sau:
Duyệt mảng A, với mỗi phần tử của mảng A lại duyệt xâu s nếu A[i] = s[j] thì ta thực hiện:
nếu là A[0] thì f[i][j] = 1;
ngược lại f[i][j] = j-start + temp;
trong đó start là vị trí gần j nhất mà f[i-1][start] > 0 và temp là giá trị f[i-1][start] (độ dài từ S[start] đến S[x] mà S[x] =A[1])
Cuối cùng KQ là min của f[n-1][j] (j=0 -> ns, với min > 0, nếu không có giá trị nào >0 thì min = 0)
Chương trình test kết quả và F[i][j] trên ideone.com
#include<cstdio> #include<cstdlib> #include <string> #include <iostream> using namespace std; int main() { string s; getline(cin,s); int n; scanf("%d",&n); char A[n]; int f[n][s.length()]; for (int i=0; i<n; i++) { scanf("%c",&A[i]); scanf("%c",&A[i]); //printf("%c ",A[i]); } //cout<<endl<<s<<endl; //printf("%dn",n); for (int i=0; i<n; i++) for (int j=0; j<s.length(); j++) f[i][j] = 0; int begin = 0, min = 0; for (int i=0; i<n; i++) { int temp = 0, check = 0, start = 0; //temp la gia tri do dai tai no, check: neu co 1 lan bang roi, start noi bat dau xet for (int j=begin; j<s.length(); j++) { if (i>0 && f[i-1][j] > 0) { start = j; temp = f[i-1][j]; } // tim start va temp if (A[i] == s[j]) { //printf("%3c%3d%3dn",A[i],i,j); if (check == 0) begin = j; // chua co ky tu nao bang thi j la noi bat dau if (i==0) f[i][j] = 1; // xet cho A[0] else { f[i][j] = j-start + temp; //vi tri hien tai - noi bat dau + gia tri do dai } check = 1; if (i==n-1) { if (f[i][j] < min || min == 0) min = f[i][j]; } } } } for (int i=0; i<n; i++) { for (int j=0; j<s.length(); j++) printf("%4d",f[i][j]); printf("n"); } printf("%d",min); return 0; }
Một cách giải khác tham khảo thêm tại đây