Ex_7_3_DetectSubstring.rar_ex

// 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); } }