给定长度的串S不超过10 ^ 5, 并设置有n个元素(n≤100) 包括ASCII字符, 区分大小写. 寻找的S连续串包含完整的字符集A和最短的长度.
(连续子串是A中字符按顺序排列且可能相距较远的字符串)
输入数据: 文件 GETSTRING.INP
第一行包含字符串 S
二线 2 是数字 n.
接下来的 N 行, 每行包含 1 集合A中的字符.
数据输出: 文件 GETSTRING.OUT
含 1 包含找到的最短子字符串的长度的单行.
例:
获取字符串.INP
你好 吉奥在
4
吨
和
克
该
获取字符串.输出
7
———————
呼叫 F[在][Ĵ] 是距字符 A 的距离[在] (该[在] = S[Ĵ]) 至 A[I-1] 在字符串 S 中.
要查找的子串的长度是距A的最短距离[ñ] 至 A[1].
˚F[在][Ĵ] 计算如下:
浏览数组A, 对于数组 A 的每个元素，浏览字符串 s if A[在] = S[Ĵ] 然后我们就这样做:
如果是A[0] 那么f[在][Ĵ] = 1;
相反[在][Ĵ] = j-开始 + 温度;
其中 start 是 f 中最接近 j 的位置[I-1][开始] > 0 temp 是 f 值[I-1][开始] (字长S[开始] 至 S[X] 其中S[X] =A[1])
最后 KQ 是 f 的最小值[N-1][Ĵ] (j=0 -> NS, 最小 > 0, 如果没有价值 >0 那么分钟= 0)

测试结果程序及F[在][Ĵ] 在 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;
}

另一种解决方案供进一步参考 这里