Horspool输出错误

Question

这是一个家庭作业问题。我有一个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; 
} 

} 

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

Answer 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，它现在检查完整的图案，当它应该的，而将失败：索引超出界限之前，而不是前一个循环那。

更多编辑：

我跳过现在并设置SYS：

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

其中给出8

但

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

是给-1。 ..

好吧，这应该做[扰流警报]

table[i] = 1; //m;