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