10 ^ 5を超えない長さの文字列Sを考えます, n個の要素を持つ、セットA(n≤100) ASCIIテーブル内の文字を含みます, 大文字と小文字を区別. Aの文字の完全なセットが含まれており、最短の長さを持っているSの連続した部分文字列を探します.
(連続する部分文字列は、Aの文字のシーケンスであり、互いに分離できます。)
入力: ファイルGETSTRING.INP
最初の行には文字列Sが含まれています
番目の行 2 数n.
次のN行, 各行には 1 エピソードAのキャラクター.
データ出力: ファイルGETSTRING.OUT
含めて 1 見つかった最短の部分文字列の長さを記録する唯一の行.
例えば:
GETSTRING.INP
こんにちは 木で
4
トン
と
グラム
ザ·
GETSTRING.OUT
7
———————
Fに電話する[で][J] 文字Aからの距離[で] (ザ·[で] = S[J]) Aへ[iは、1] 文字列S内.
検索する部分文字列の長さは、Aからの最短距離です[N] Aへ[1].
F[で][J] 次のように計算されます:
アレイAを参照, 配列Aの各要素について、Aの場合は文字列sを参照します[で] = S[J] それから私たちはします:
それがAなら[0] その後f[で][J] = 1;
反対のf[で][J] = j-start + 一時;
ここで、startはjに最も近い位置で、f[iは、1][開始] > 0 そしてtempはf値です[iは、1][開始] (Sからの長さ[開始] Sへ[X] 手S[X] = A[1])
最後に、KQはfの最小値です[-1][J] (j = 0-> NS, 分あり > 0, 値がない場合 >0 その後、min = 0)

プログラムのテスト結果とF[で][J] 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;
}

参考のための別のソリューション ここに