java 数据结构串

                     串是若干个字符组成的有限序列。大部分的软件系统都会频繁使用串。串也是一种线性结构。和线性表不同的是，串的操作特点是一次操作若干个数据元素，即一次操作一个字符串。串通常采用顺序存储结构存储，模式匹配是串的一个非常重要的操作，但是模式匹配的时间效率很差。Brute-Force和Kmp算法是两种最经典的串模式匹配算法。

串的基本概念和抽象数据类型

         串（也称字符串）是由n(n>=0)个字符串组成的有限序列。抽象含义的串一般记为s="s1,s2.....sn",其中s为串名，n 为串长度，双引号括起来的字符序列成为串值。每个字符si（0<i<n）可以是任意的Unicode码字符，一般是字母、数子、标点符号等屏幕可显示的字符。

       一个串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为该子串的主串。

      串也是一种特殊的线性表。和线性表相比，串的数据元素以及数据元素之间的逻辑关系和线性表完全相同，其差别是：（1）线性表的数据元素可以是任意数据类型，而字符串的数据类型只允许是字符类型。（2）线性表一次操作一个数据元素，而串一次操作若干个数据元素，即一个字符串。如果每次操作的子串长度固定为1，那么串就是数据类型固定为字符型的线性表。

     一个字符在一个串中的位置序号称为该字符在串中的位置。可以比较任意两个串的大小。我们称两个串相等，当且仅当这两个串的值完全相等。两个串的值完全相等意味着两个串不仅是长度相等，而且各个位置字符都想等。

串的模式匹配算法

         串的查找操作也称为串的模式匹配操作。模式匹配操作的具体含义是：在主串中，从开始的查找是否存在子串，如在主串中查找到一个与模式串相同的子串则查找成功。如在主串中未查找到一个与模式串相同的则称为查找失败。当模式匹配成功，返回第一个字符在主串中的位置，当模式匹配失败时函数返回-1.

Brute-Force算法源代码：

package com.bruteforce; 
/**  
 * 字符串匹配模式算法Brute-Force算法，此算法每次比较都会回退  
 * @author hhzxj2008  
 * */   
 
public class StringMatch { 
 
	public static void main(String[] args) { 
               int result=match("123456","45"); 
               System.out.println("字符串匹配结果："+result); 
	} 
	/**  
	     * 相当于java.lang.String的indexOf,采用Brute-Force算法  
	     * */   
 
	public static int match(String str, String substr) { 
		// 1.字串的第一字符与主串的第一个字符比较，若不匹配字串的第一个字符和主串的第二个字符比较 
		// 2.若字串的第一个字符与主串的某一位置上字符串匹配，则将字串的第二个字符与主串该位的下一位置 
		// 进行比较，依次类推。遇到不相等，则重复第一步。 
		int index = -1; 
		boolean match = true; 
		for (int i = 0; i <= str.length() - substr.length(); i++) {// str 
			match = true; 
			for (int j = 0; j < substr.length(); j++) {// substr 
				if (str.charAt(i + j) != substr.charAt(j)) { 
					match = false; 
				} 
			} 
			if (match) { 
				index = i; 
				break; 
			} 
		} 
		return index; 
	} 
 
}

KMP 算法源代码：

package com.bruteforce; 
 
public class KMPTest { 
 
	/**  
	 * Java实现KMP算法  
	 *   
	 * 思想：每当一趟匹配过程中出现字符比较不等，不需要回溯i指针，   
	 * 而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远   
     * 的一段距离后，继续进行比较。  
	 *   
	 * 时间复杂度O(n+m)  
	 *   
	 * @author xqh  
	 *   
	 */   
 
	public static void main(String[] args) { 
		// TODO Auto-generated method stub 
            String example="1122334455"; 
            String result="23456"; 
              
            char[] examples=example.toCharArray(); 
            char[] results=result.toCharArray(); 
             
            System.out.println("KMP算法匹配的结果："+KMP_Index(examples,results)); 
	} 
	 
	 /**  
	     * 获得字符串的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; // 返回模式串在主串中的头下标    
	    }   
 
	 
 
}