ようこそ ゲスト さん、新規登録（無料）して気になる疑問を解決しませんか？
はじめての方へ｜ヘルプ｜FAQ
スポンサーサイト（詳細）

質問
QNo.3966478 テキストの中から与えられた文字を含む最短の文字列を求める為のアルゴリズムについて
質問者：BOMBEI 例）Thatisanotebook.
というテキストがあったとします。
与えられた文字がost(順番は構わない)だとすると、ostを含む最短の文字列はsanotです。

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

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

どなたかご教授お願いします。
困り度：
  • すぐに回答を！
質問投稿日時：
08/04/22 01:37
最新から表示｜回答順に表示

回答
ANo.2 ★解答( 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 );
　}
}
注：インデントに全角空白を用いています。
　　タブに一括変換して下さい。
回答者：yama5140
種類：アドバイス
どんな人：一般人
自信：参考意見
回答日時：
08/04/22 12:19
この回答への補足この回答に補足をつける(質問者のみ)
この回答へのお礼この回答にお礼をつける(質問者のみ)

回答
ANo.1 >for文を使った簡単なものは作れるのですが、処理が遅すぎて困っています。
じゃあ、まずはそのソースを補足にどうぞ。
回答者：koko_u_
種類：補足要求
どんな人：一般人
自信：参考意見
回答日時：
08/04/22 01:46
この回答への補足この回答に補足をつける(質問者のみ)
この回答へのお礼この回答にお礼をつける(質問者のみ)
 
最新から表示｜回答順に表示
スポンサーサイト（詳細）
このページのトップへ