大话数据结构——串

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解串。

串

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

串的存储结构

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

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

朴素的模式匹配算法

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

/**
 * 朴素的模式匹配算法
 */
public class Match {
    public int match(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 ="Star is good man";
        String t =" good";
        Match matching = new Match();
        System.out.println(matching.match(s, t, 0));
        System.out.println(matching.match(s, t, 8));
    }
}

KMP模式匹配算法

/**
 * KMP模式匹配算法
 */
public class MatchKMP {
    public int matchKMP(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) {
        String s ="Star is good man";
        String t =" good";
        MatchKMP matching = new MatchKMP();
        System.out.println(matching.matchKMP(s, t, 0));
        System.out.println(matching.matchKMP(s, t, 8));
    }
}

改进的KMP模式匹配算法

/**
 * 改进的KMP模式匹配算法
 */
public class MatchImproveKMP {
    public int matchImproveKMP(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) {
        String s ="Star is good man";
        String t =" good";
        MatchImproveKMP matching = new MatchImproveKMP();
        System.out.println(matching.matchImproveKMP(s, t, 0));
        System.out.println(matching.matchImproveKMP(s, t, 8));
    }
}