1

私は長い文といくつかの単語（文で検索する）を与えました。その文で検索するすべての単語を含む文の最小部分を見つけて、その部分を印刷する必要があります。

私はそれを試しました.1.最初に、与えられた文からすべての単語のすべての場所（インデックス）を取得します。2. 次に、これらの単語のインデックスから最小部分を見つけようとします。

しかし、2番目の部分の実装に問題があります。だから私はそれについてのアドバイスが欲しいか、それを速くすることができる他のアルゴリズムを提案してください。

import java.util.*;
import java.io.*;
public class ShotestSubSegment2 
{
static SearchStr[] search;
static String copystr;
public static void main(String s[])
{
try
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        copystr = str.substring(0).toLowerCase();
        int k = Integer.parseInt(in.readLine());
        search = new SearchStr[k];
        for(int i=0;i<k;i++)
        {
            search[i] = new SearchStr(in.readLine().toLowerCase());
            getIndicesOf(search[i]);
            if(search[i].noOfElements()==0)
            {
                System.out.println("No Segments Found");
                return;
            }
        }
        searchSmallestPart();//Dont getting Idea Of this

    }
    catch(Exception x){}
}

public static void getIndicesOf(SearchStr searchS) 
{
    String searchStr = searchS.getName();
    int startIndex = 0, searchStrLen=0;
    int index;
    searchStr = searchStr.toLowerCase();
    searchStrLen = searchStr.length();
    while ((index = copystr.indexOf(searchStr, startIndex)) > -1) 
    {
        searchS.add(index);
        startIndex = index + searchStrLen;
    }
}

}
4

4 に答える 4

0

このクラスの使用：

class FoundToken  {
   int start;
   end start;
   String word;
   int endOfCompleteSequence;
}

1）開始インデックスと終了インデックスを使用して、見つかったすべてのトークンをリストに保存します

2）これらのリスト項目のそれぞれについて、（リスト内の）次のトークンから構築され、必要なすべてのトークンを含む最初の完全なシーケンスを取得します

3）それらのシーケンスの最短を取ります（に基づいてendOfCompleteSequence-start)。

于 2012-06-27T10:52:15.010 に答える
0

単語ごとに、その単語が現れる位置をリストに格納します。

word1 - word1 が見つかった位置のリスト 1 word2 - word2 が見つかった位置のリスト 2 ...

Pstart は、すべての単語の有効な位置の組み合わせの位置のリストから最小の位置であり、Pend は最大の位置です。テキスト内で見つかったすべての単語の組み合わせを生成するには、バックトラッキングを使用します。

私は自分自身を明確にしたことを願っています。

于 2012-06-27T10:57:03.343 に答える
0

これが私のアルゴリズムです。少し素人かもしれませんが、それが私が理解した最も基本的なアプローチです。

  1. 入力後、単語をループ スローし、リストされた単語と一致するものを確認します。リストされた単語を格納する配列に進みます。

  2. 一致が見つかるとすぐに、その位置をマークし、その位置から別のスキャンを開始して、一致を確認します。一致した単語をリストから並行して削除し、リストのすべての単語が見つかるまでチェックします。次の単語が見つかるまで、すべての単語 (中間の単語も) を文字列に追加します。この特定のループは、リストされた単語配列のすべての要素が null になるまで続きます。

  3. 最も内側のスキャンが完了したものは、文字列を格納するため、別の配列 (文字列 sol_array など) に見つかります。前のループを続行します (前のループは (original_string.length() - Listed_word_array.length) 回実行されます)。

  4. 最も外側のループが完了したら、sol_array のスキャンを実行し、最小の文字列の長さを確認します。その文字列が答えです。

于 2013-04-27T22:09:08.503 に答える