给定长度的串S不超过10 ^ 5, 并设置有n个元素(n≤100) 包括ASCII字符, 区分大小写. 寻找的S连续串包含完整的字符集A和最短的长度.
(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
含 1 dòng duy nhất ghi độ dài chuỗi con ngắn nhất tìm được.
例:
GETSTRING.INP
你好 the gio在
4
吨
和
克
该
GETSTRING.OUT
7
———————
Gọi F[在][Ĵ] là khoảng cách từ ký tự A[在] (该[在] = S[Ĵ]) đế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 A[1].
˚F[在][Ĵ] đượ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[在] = S[Ĵ] thì ta thực hiện:
nếu là A[0] 那么f[在][Ĵ] = 1;
ngược lại f[在][Ĵ] = j-start + 温度;
trong đó start là vị trí gần j nhất mà f[I-1][开始] > 0 và temp là giá trị f[I-1][开始] (độ dài từ S[开始] đến S[X] mà S[X] =A[1])
Cuối cùng KQ là min của f[N-1][Ĵ] (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[在][Ĵ] 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 这里