ex_7_3_detectsubstring.java

识别子串 模式匹配 KMP算法 输入两个String

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