java - Horspool 输出错误

Question

这是一个家庭作业问题。我有一个java程序来计算某个模式/字符串是否在用户输入的文本字符串中。该程序可以运行，但始终输出 -1，如果模式字符串不在指定文本中，则应输出 -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;
}

}

任何帮助将不胜感激!非常感谢!

Answer 1

It always outputs a -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 会在它应该的时候失败:在索引超出范围之前，而不是在此之前的一个循环。

更多编辑:

我现在跳过系统并设置:

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

得出 8

但是

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

给出-1...

好的，这样就可以了[剧透警告]

table[i] = 1; //m;