// 093026 P225 KMP fail构造 & StringMatch
// Java没有全局变量! 如下定义的必须 static 的是一旦赋值不能随便变的.
import javax.swing.JOptionPane;
public class Ex_7_3_DetectSubstring {
/**
* @param args
*/
static String Text;
static int n = Text.length();
static String Pattern;
static int m = Pattern.length();
public static int[] KMPSetup(String Pattern) {
int k, s;
char P[] = Pattern.toCharArray();
int fail[] = new int[m];
fail[0] = -1;
for(k = 1; k < m; k++){
s = fail[k - 1];
while(P[s + 1] != P[k] && s >= 0)
s = fail[s];
if(P[s + 1] == P[k])
fail[k] = s + 1;
else
fail[k] = -1;
}
return fail;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String PatternString = JOptionPane.showInputDialog("Enter the Pattern String:\n", JOptionPane.QUESTION_MESSAGE);
char[] Pattern = PatternString.toCharArray();
String TextString = JOptionPane.showInputDialog("Enter the Text String:\n", JOptionPane.QUESTION_MESSAGE);
char[] Text = TextString.toCharArray();
int[] fail = KMPSetup(PatternString);
// 测试数据
// for(int value: fail)
// System.out.print(value + " ");
System.out.println();
int t = 0, p = 0;
while(t < n && p < m){
if(Text[t] == Pattern[p]){
t++;
p++;
}
else if(p == 0)
t++;
else
p = fail[p - 1] + 1;
}
if(p < m)
JOptionPane.showMessageDialog(null, "Not match!", TextString, JOptionPane.INFORMATION_MESSAGE);
else
JOptionPane.showMessageDialog(null, "Matched @: " + (t - m + 1) + " of the text string.", TextString, JOptionPane.INFORMATION_MESSAGE);
}
}