阅读大话数据结构（4）

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解串，代码均为自己实现。

串

串（string）是由零个或多个字符组成的有限序列，又名字符串。

串的存储结构

​ 串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。 用“\0”来表示串的终结，不计入串长度，但是计入数组长度。 两个长度不同的串不可能相等。

​ 串的链式存储结构要考虑一个结点是存放一个字符（会造成很大的空间浪费）还是多个字符。除了链接串与串的操作有一定方便外，总的来说不如顺序存储量或，性能也不如顺序存储结构好。

朴素的模式匹配算法

串的模式匹配：串的定位操作。
时间复杂度：O(1)–最好；O(n+m)–平均；O(n-m+1)*m–最不好

public class Index {
	public int index(String s , String t , int post){
		if(s == null || t == null){
			return -1;
		}
		int len1 = s.length();
		int len2 = t.length();
		int i = post;
		int j = 0;
		while (i < len1 && j < len2) {
			if (s.charAt(i) == t.charAt(j)) {
				i++;
				j++;
			}else{
				i = i - j + 1;
				j = 0;
			}
		}
	    if (j >= len2){
			return i - len2;
		}else{
			return -1;
		}
	}
	public static void main(String[] args) {
		String s ="luckylau is good man";
		String t =" good";
		Index Index = new Index();
		System.out.println(Index.index(s, t, 0));
		System.out.println(Index.index(s, t, 8));
	}
}

KMP模式匹配算法

public class IndexKMP {
	public int indexKMP(String s ,String t ,int post){
		if(s == null || t == null){
			return -1;
		}
		int len1 = s.length();
		int len2 = t.length();
		int i = post;
		int j = 0;
		int[] next = getNext(t);
		while (i < len1 && j < len2) {
			if (j== -1 || s.charAt(i) == t.charAt(j)) {
				i++;
				j++;
			}else{
				j = next[j];
			}
		}
	    if (j >= len2){
			return i - len2;
		}else{
			return -1;
		}
	}
	
	private int[] getNext(String t){
		int [] next = new int [t.length()];
		int i = 0;
		int j = -1;
		next[i] = j;
		while (i < t.length() - 1){
			if (j == -1 || t.charAt(i) == t.charAt(j)){
				i++;
				j++;
				next[i] =j;		
			}else{
				j = next[j];
			}
		}
		return next;
		
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s ="luckylau is good man";
		String t =" good";
		IndexKMP Index = new IndexKMP();
		System.out.println(Index.indexKMP(s, t, 0));
		System.out.println(Index.indexKMP(s, t, 8));

	}

}

改进版

public class IndexKMP {
	public int indexKMP(String s ,String t ,int post){
		if(s == null || t == null){
			return -1;
		}
		int len1 = s.length();
		int len2 = t.length();
		int i = post;
		int j = 0;
		int[] next = getNext(t);
		while (i < len1 && j < len2) {
			if (j== -1 || s.charAt(i) == t.charAt(j)) {
				i++;
				j++;
			}else{
				j = next[j];
			}
		}
	    if (j >= len2){
			return i - len2;
		}else{
			return -1;
		}
	}
	
	private int[] getNext(String t){
		int [] next = new int [t.length()];
		int i = 0;
		int j = -1;
		next[i] = j;
		while (i < t.length() - 1){
			if (j == -1 || t.charAt(i) == t.charAt(j)){
				i++;
				j++;
				if(t.charAt(i) == t.charAt(j)){
					next[i] = next[j];
				}else{
					next[i] = j;
				}
						
			}else{
				j = next[j];
			}
		}
		return next;
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s ="luckylau is good man";
		String t =" good";
		IndexKMP Index = new IndexKMP();
		System.out.println(Index.indexKMP(s, t, 0));
		System.out.println(Index.indexKMP(s, t, 8));

	}

}

串相关算法题

以下是涉及到串我的github的算法题集合

N-Series