1

例：与えられた文がある場合：そして、与えられた単語myとeugene
My name is not eugene. my pet name is not eugene.
を含む文の最小部分を検索する必要がある 場合、答えはになります 。 大文字や小文字、特殊な文字や数字をチェックする必要はありません。 コードを貼り付けましたが、一部のテストケースで間違った答えが返ってきました。eugene. my

誰もがコードの問題が何であるかを知ることができます。私はそれが間違っているテストケースを持っていません。

import java.io.*;
import java.util.*;
public class ShortestSegment 
{
static String[] pas;
static String[] words;
static int k,st,en,fst,fen,match,d;
static boolean found=false;
static int[] loc;
static boolean[] matches ;
public static void main(String s[]) throws IOException
{
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    pas = in.readLine().replaceAll("[^A-Za-z ]", "").split(" ");
    k = Integer.parseInt(in.readLine());
    words = new String[k];
    matches = new boolean[k];
    loc = new int[k];
    for(int i=0;i<k;i++)
    {
        words[i] = in.readLine();
    }
    en = fen = pas.length;
    find(0);
    if(found==false)
    System.out.println("NO SUBSEGMENT FOUND");
    else
    {
        for(int j=fst;j<=fen;j++)
            System.out.print(pas[j]+" ");
    }

}
private static void find(int min)
{
    if(min==pas.length)
        return;
    for(int i=0;i<k;i++)
    {
        if(pas[min].equalsIgnoreCase(words[i]))
        {
            if(matches[i]==false)
            {
                loc[i]=min;
                matches[i] =true;
                match++;
            }
            else
            {
                    loc[i]=min;
            }
            if(match==k)
            {
                en=min;
                st = min();
                found=true;
                if((fen-fst)>(en-st))
                {
                    fen=en;
                    fst=st;
                }
                match--;
                matches[getIdx()]=false;
            }
        }
    }
    find(min+1);
}
private static int getIdx()
{
    for(int i=0;i<k;i++)
    {
        if(words[i].equalsIgnoreCase(pas[st]))
            return i;
    }
    return -1;
}
private static int min()
{
    int min=loc[0];
    for(int i=1;i<loc.length;i++)
        if(min>loc[i])
            min=loc[i];
    return min;
}


}
4

4 に答える 4

0

別の方法で処理できると思います。まず、一致する結果を見つけ、現在の結果へのバインドを最小化してから、現在の結果から一致する結果を見つけます。次のようにコーディングできます。

/**This method intends to check the shortest interval between two words
 * @param s : the string to be processed at
 * @param first : one of the words
 * @param second : one of the words
 */
public static void getShortestInterval(String s , String first , String second)
{
    String situationOne = first + "(.*?)" + second;
    String situationTwo = second + "(.*?)" + first;

    Pattern patternOne = Pattern.compile(situationOne,Pattern.DOTALL|Pattern.CASE_INSENSITIVE);
    Pattern patternTwo = Pattern.compile(situationTwo,Pattern.DOTALL|Pattern.CASE_INSENSITIVE);

    List<Integer> result = new ArrayList<Integer>(Arrays.asList(Integer.MAX_VALUE,-1,-1));
    /**first , test the first choice*/
    Matcher matcherOne = patternOne.matcher(s);
    findTheMax(first.length(),matcherOne, result);
    /**then , test the second choice*/
    Matcher matcherTwo = patternTwo.matcher(s);
    findTheMax(second.length(),matcherTwo,result);

    if(result.get(0)!=Integer.MAX_VALUE)
    {
        System.out.println("The shortest length is " + result.get(0));
        System.out.println("Which start @ " + result.get(1));
        System.out.println("And end @ " + result.get(2));
    }else
        System.out.println("No matching result is found!");
}

private static void findTheMax(int headLength , Matcher matcher , List<Integer> result) 
{
    int length = result.get(0);
    int startIndex = result.get(1);
    int endIndex = result.get(2);

    while(matcher.find())
    {
        int temp = matcher.group(1).length();
        int start = matcher.start();
        List<Integer> minimize = new ArrayList<Integer>(Arrays.asList(Integer.MAX_VALUE,-1,-1));
        System.out.println(matcher.group().substring(headLength));
        findTheMax(headLength, matcher.pattern().matcher(matcher.group().substring(headLength)), minimize);
        if(minimize.get(0) != Integer.MAX_VALUE)
        {
            start = start + minimize.get(1) + headLength;
            temp = minimize.get(0);
        }

        if(temp<length)
        {
            length = temp;
            startIndex = start;
            endIndex = matcher.end();
        }
    }

    result.set(0, length);
    result.set(1, startIndex);
    result.set(2, endIndex);
}

これは、2つの単語の順序に関係なく、2つの状況を処理できることに注意してください。

于 2012-07-03T13:57:02.447 に答える
0

次のコード (junit):

@Test
public void testIt() {
    final String s = "My name is not eugene. my pet name is not eugene.";
    final String tmp = s.toLowerCase().replaceAll("[^a-zA-Z]", " ");//here we need the placeholder (blank)
    final String w1 = "my "; // leave a blank at the end to avoid those words e.g. "myself", "myth"..
    final String w2 = "eugene ";//same as above
    final List<Integer> l1 = getList(tmp, w1); //indexes list
    final List<Integer> l2 = getList(tmp, w2);
    int min = Integer.MAX_VALUE;
    final int[] idx = new int[] { 0, 0 };

    //loop to find out the result
    for (final int i : l1) {
        for (final int j : l2) {
            if (Math.abs(j - i) < min) {
                final int x = j - i;
                min = Math.abs(j - i);
                idx[0] = j - i > 0 ? i : j;
                idx[1] = j - i > 0 ? j + w2.length() + 2 : i + w1.length() + 2;
            }
        }

    }

    System.out.println("indexes: " + Arrays.toString(idx));
    System.out.println("result: " + s.substring(idx[0], idx[1]));
}

private List<Integer> getList(final String input, final String search) {
    String t = new String(input);
    final List<Integer> list = new ArrayList<Integer>();
    int tmp = 0;
    while (t.length() > 0) {
        final int x = t.indexOf(search);

        if (x < 0 || x > t.length()) {
            break;
        }
        tmp += x;
        list.add(tmp);
        t = t.substring(search.length() + x);

    }
    return list;

}

出力を与える：

indexes: [15, 25]
result: eugene. my

インラインコメント付きのコードはかなり理解しやすいと思います。基本的に、インデックス+語長で遊んでいます。

ノート

  • 「Not Found」ケースは実装されていません。
  • コードはアイデアを示しているだけで、最適化できます。たとえば、少なくとも 1 つの ab​​s() を保存できます。等...

それが役に立てば幸い。

于 2012-07-02T22:44:01.000 に答える
0

アルゴリズムを使用Knuth Morris Prattして、テキスト内のすべての単語のすべての出現箇所のインデックスを見つけることができます。長さ N および M 語 (w1 ... wM) のテキストがあるとします。アルゴリズムを使用KMPすると、配列を取得できます。

occur = string[N];
occur[i] = 1, if w1 starts at position i
...
occur[i] = M, if wM starts at position i
occur[i] = 0, if no word from w1...wM starts at position i

この配列をループし、ゼロ以外のすべての位置から他の M-1 単語を前方検索します。

これはおおよその擬似コードです。考え方を理解するだけです。Javaで再コーディングしただけでは、間違いなく機能しません。

for i=0 to N-1 {
 if occur[i] != 0 {
  for j = i + w[occur[i] - 1].length - 1 { // searching forward
   if occur[j] != 0 and !foundWords.contains(occur[j]) {
    foundWords.add(occur[j]);
    lastWordInd = j;
    if foundWords.containAllWords() break;
   }
   foundTextPeaceLen = j + w[occur[lastWordInd]].length - i;
   if foundTextPeaceLen < minTextPeaceLen {
    minTextPeaceLen = foundTextPeaceLen;
    // also remember start and end indexes of text peace
   }
  }
 }
}
于 2012-10-08T10:45:41.650 に答える