1

これはちょっとした宿題です。ユーザーが入力したテキスト文字列に特定のパターン/文字列が含まれているかどうかを計算するJavaプログラムがあります。プログラムは動作しますが、常に -1 を出力します。これは、パターン文字列が指定されたテキストにない場合に出力されるはずです。何が機能していないのか一生わからないので、何を修正する必要があるかについてのヒントをいただければ幸いです。

これが私のコードです：

import java.util.Scanner;

/**
 * @author Mouse
 *
 */
public class horspool {

/**
 * @param args
 */
public static void main(String[] args) 
{
    Scanner scanIn = new Scanner (System.in);

    //The text to search for the phrase in
    String t = "";

    //The phrase/pattern to search for
    String p = "";

    System.out.println(" ");
    System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
    System.out.println("Harspool's Algorithm: ");
    System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
    System.out.println(" ");
    System.out.println("Please enter the full text: ");
    t = scanIn.nextLine();
    System.out.println("Please enter the pattern to search for: ");
    p = scanIn.nextLine();

    char[] text = new char[t.length()];
    char[] pattern = new char[p.length()];

    for (int i = 0; i < text.length; i++)
    {
        text[i] = t.charAt(i);
    }

    for (int i = 0; i < pattern.length; i++)
    {
        pattern[i] = p.charAt(i);
    }

    int newChar[] = new int[256];

    for(int i=0; i < 256; i++) 
    {
        newChar[i]=0;
    }

    for (int i = 0; i < text.length; i++)
    {
        newChar[t.charAt(i) % 256]++;
    }

    for (int i = 0; i < pattern.length; i++)
    {
        newChar[p.charAt(i) % 256]++;
    }

    int index = HorspoolMatching(pattern, text);

    System.out.println("Index: " + index);
}

public static int[] ShiftTable(char[] p) 
{
    int m = p.length;

    //Table filled with shift sizes for each individual letter.
    int[] table = new int[256];

    for (int i = 0; i < table.length; i++)
    {
        table[i] = m;
    }
    for (int j = 0; j < m - 1; j++)
    {
        for (int a = 0; a < p.length; a++)
        {
            if (p[j] == p[a])
            {
                table[a] = (m - 1 - j);
            }
        }
    }
    return table;
}


public static int HorspoolMatching(char[] p, char[] t) 
{
    int [] table = ShiftTable(p);
    int m = p.length;
    int i = m - 1;
    int n = t.length;
    int temp = 0;
    int k = 0;
    int count = 0;

    while (i <= n - 1)
    {
        k = 0;

        while (t[i - k] == p[m - 1 - k] && k < m - 1) 
        {
            System.out.println("In second while");
            k++;
        }   
        if (k == m)
        {
            return (i - m + 1);
        } 
        else
        {
            for (int a = 0; a < t.length; a++)
            {
                if (t[i] == t[a])
                {
                    temp = table[a];
                }
            }
            i = i + temp;
        }
    }
    return -1;
}

}

どんな助けでも大歓迎です！本当にありがとう！

4

1 に答える 1

1

常に-1を出力します

HorspoolMatching の return ステートメントを確認してください。

編集：わかりました、私はだまされました、ごめんなさい。

私が変わったとき

while (t[i - k] == p[m - 1 - k] && k < m - 1)

に

while ( k < m && t[i - k] == p[m - 1 - k])

それは働き始めました。

k < m - 1 の問題は、ループを停止するのが早すぎて、完全なパターンを実際にチェックしていなかったため、一致しないことでした。

&& の最初の条件に移動し、-1 を削除することで、完全なパターンをチェックするようになり、while が想定どおりに失敗するようになりました。

その他の編集:

私は今のところsysをスキップして設定しています：

String t = "lklklklkabcdabababcd";
String p = "ab";

8を与える

しかし

String t = "lklklklkabcdabababcd";
String p = "abc";

-1を与えています...

さて、これでうまくいくはずです[ネタバレ注意]

table[i] = 1; //m;
于 2013-03-25T18:55:03.433 に答える