字符串匹配算法 BF/KMP实现/栈、行列

字符串匹配算法 BF/KMP实现/栈、队列

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;



public class test1 {
	public static void main(String[] args) {
		Stack<String> stack = new Stack<String>();

		Queue<String> queue = new LinkedList<String>();
		//Queue< String> queue2 = new LinkedList<String>();
		for (String string : "my dog has fleas".split(" ")) {
			stack.add(string);
			//stack.push(string);
			queue.add(string);
		}
		while (!stack.isEmpty()&&!queue.isEmpty()) {
			System.out.println("stack  :  "+stack.pop());	
			System.out.println("queue  ：     "+queue.remove());
		}
		System.out.println();

		String a = "abafsdag";
		String b = "ag";

		BF(a, b);//BF

		char [] aa = a.toCharArray();
		char [] bb = b.toCharArray();
		System.out.println(KMP_Index(aa, bb));

	}
	/**
	 * KMP算法
	 */
	/** 
	 * 获得字符串的next函数值 
	 *  
	 * @param t 
	 *            字符串 
	 * @return next函数值 
	 */  
	public static int[] next(char[] t) {  
		int[] next = new int[t.length];  
		next[0] = -1;  
		int i = 0;  
		int j = -1;  
		while (i < t.length - 1) {  
			if (j == -1 || t[i] == t[j]) {  
				i++;  
				j++;  
				if (t[i] != t[j]) {  
					next[i] = j;  
				} else {  
					next[i] = next[j];  
				}  
			} else {  
				j = next[j];  
			}  
		}  
		return next;  
	}  

	/** 
	 * KMP匹配字符串 
	 *  
	 * @param s 
	 *            主串 
	 * @param t 
	 *            模式串 
	 * @return 若匹配成功，返回下标，否则返回-1 
	 */  
	public static int KMP_Index(char[] s, char[] t) {  
		int[] next = next(t);  
		int i = 0;  
		int j = 0;  
		while (i <= s.length - 1 && j <= t.length - 1) {  
			if (j == -1 || s[i] == t[j]) {  
				i++;  
				j++;  
			} else {  
				j = next[j];  
			}  
		}  
		if (j < t.length) {  
			return -1;  
		} else  
			return i - t.length; // 返回模式串在主串中的头下标  
	}  

	/**
	 * BF算法匹配查找
	 * @param a
	 * @param b
	 */
	public static void BF(String a ,String b) {
		int m ,n ,flag=0;
		for (int i = 0; i < a.length() ;i++) {
			m=i;
			for (int k = 0; k < b.length();k++) {
				n=k;
				if (a.charAt(m)==b.charAt(n) && m < a.length() && n < b.length() && flag==0) {
					m++;
					n++;
					if (n==b.length()) {
						flag = 1;
						System.out.println("起始位置：   "+i);
						System.out.println("true");
					}

				}
				else {
					break;
				}
			}
		}
		if (flag==0) {
			System.out.println("没有重复的  ");
		}
	}
}