テキストの中から与えられた文字を含む最短の文字列を求める為のアルゴリズムについて

質問

例）Thatisanotebook.
というテキストがあったとします。
与えられた文字がost(順番は構わない)だとすると、ostを含む最短の文字列はsanotです。

このときsanotと導くためのアルゴリズムが分かりません。

for文を使った簡単なものは作れるのですが、処理が遅すぎて困っています。

どなたかご教授お願いします。

回答No.2

yama5140

★解答( sanot )の頭は、検索文字( o, s, t )である。

　このことから、対象となる文字列 Thatisanotebook
　の頭から、検索文字( o, s, t )以外を除外していく（◆）。

★残った文字列( tisanotebook )から、検索文字( o, s )の内、
　最後に検索した場所（▲最後－トップ）を、メモしておく（●）。
　（１つの解答が得られた）

★次に、◆と同様に、検索文字( o, s, t )以外を除外し、
　残った文字列( sanotebook )から、・・（略：繰り返し）

てのは如何でしょう。

＞for文を使った簡単なものは作れるのですが、処理が遅すぎて困っています。

　「丸投げ」ではないので、「瞬時」に結果の出るソースを・・。

★参考になればよいのですが（ずいぶん長くて・・申し訳ない）
-----------------------------------------------------
#include <stdio.h>
#include <string.h>

typedef　struct{
　int　iLen;
　char　cAns[32];
}MEMO;

MEMO　sWork[10];

int　UseTotal( int iUse[] )
{
　int　i, iTotal = 0;

　for( i = 0; i < 8; i++ )　iTotal += iUse[i];

　return( iTotal );
}
void　main()
{
　char　cTaisyou[32] = "Thatisanotebook";
　char　cKensaku[ 8] = "ost";
　int　i, j, iLen, iTop, iHead;
　int　iUse[8], iKenCnt = 0, iMojiSu;

　iMojiSu = strlen( cKensaku );　// 検索文字数

　for( iTop = 0; iTop < 32; iTop++ ){

　　if( 0x00 == cTaisyou[iTop] )　break;

　　iHead = 0;

　　for( i = 0; i < iMojiSu; i++ ){

　　　if( cKensaku[i] == cTaisyou[iTop] ){

　　　　iHead = 1;

　　　　break;
　　　}
　　}
　　if( 0 == iHead )　continue;　// ◆

　　for( i = 0; i < 8; i++ )　iUse[i] = 0;　// 初期化

　　for( j = iTop; j < 32; j++ ){　// 対象文字列を１つずつ

　　　if( 0x00 == cTaisyou[j] )　break;

　　　for( i = 0; i < iMojiSu; i++ ){

　　　　if( iUse[i] )　continue;

　　　　if( cKensaku[i] == cTaisyou[j] ){

　　　　　iUse[i]++;　// 検索文字使用済み

　　　　　if( UseTotal( iUse ) == iMojiSu ){　// ●

　　　　　　iLen = j - iTop + 1;　// ▲

　　　　　　strcpy( sWork[iKenCnt].cAns, &cTaisyou[iTop] );

　　　　　　sWork[iKenCnt].cAns[iLen] = 0x00;
　　　　　　sWork[iKenCnt].iLen = iLen;

　　　　　　iKenCnt++;
　　　　　}
　　　　　break;
　　　　}
　　　}
　　}
　}
　for( i = 0; i < iKenCnt; i++ ){　// ●出力

　　printf( "%2d %s\n", sWork[i].iLen, sWork[i].cAns );
　}
}
注：インデントに全角空白を用いています。
　　タブに一括変換して下さい。

回答No.1

koko_u_

>for文を使った簡単なものは作れるのですが、処理が遅すぎて困っています。
じゃあ、まずはそのソースを補足にどうぞ。