Java数据结构-串及其应用-KMP模式匹配算法

绝地灬酷狼 2022-08-02 15:52 153阅读 0赞

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

定义的解释：  
  串中的字符数目n称为串的长度，定义中谈到“有限”是指长度n是一个有限的数值。  
  零个字符的串称为空串（null string），它的长度为零，可以直接用两双引号一表示，也可以用希腊Φ字母来表示。  
  所谓的序列，说明串的相邻字符之间具有前驱和后继的关系。

下面是串的一些概念性东西：

空格串，是只包含空格的串。注意它与空串的区别，空格串是有内容有长度的，而且可以不止一个空格。

子串与主串，串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。子串在主串中的位置就是子串的第一个字符在主串中的序号。

串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。比较两个串是否相等，必须是它们串的长度以及它们各个对应位置的字符都相等时，才算是相等。

**串与线性表的比较**：  
  两者的逻辑结构比较相似，不同的是串针对的是字符集（即串中的元素都是字符）。  
  线性表更关注的是单个元素的操作，比如査找一个元素，插入或删除一个元素，但串中更多的是査找子串位置、得到指定位置子串、替换子串等操作。  
  串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。

注意：  
  串的连接操作，需要注意串长问题，可能遇到的问题就是两个串连接后会不会溢出，所以需要进行截断操作。

查找子串在主串中的位置，操作如下：  
 1. 设i用于主串s1中当前位置下标值，j用于子串sub中当前位置下标值。  
 2. 首先我们比较s1\[1\]与sub\[1\]，如果相同的话，可能子串就开始了。  
 3. 如果不相等，那么子串仍然是从sub\[1\]开始，而主串s1则以s1\[2\]与其比较。  
 4. 如果连续出现子串长度次或以上匹配，那么就找到子串了，此时的j必然大于子串长度sub\[0\]。

KMP模式匹配算法：  
  这个东西有些难懂，下面是我的学习的时候的一些经验，希望对大家有所帮助。

KMP模式匹配算法，不懂的话建议去鱼C看视频：[http://study.163.com/course/courseMain.htm?courseId=468002][http_study.163.com_course_courseMain.htm_courseId_468002]，讲的很不错，很详细；  
然后对于前后缀视频里面讲的还不是很详细清楚，不好理解的话可以去看阮一峰的这篇文章[http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt\_algorithm.html][http_www.ruanyifeng.com_blog_2013_05_Knuth_E2_80_93Morris_E2_80_93Pratt_algorithm.html]

还有两篇KMP推荐：  
从头到尾彻底理解KMP（2014年8月22日版） - 结构之法 算法之道 - 博客频道 - CSDN.NET  
[http://blog.csdn.net/v\_july\_v/article/details/7041827][http_blog.csdn.net_v_july_v_article_details_7041827]

KMP算法学习初步 | 海虹不老阁——遥望北方的狼  
[http://haihongblog.com/archives/911.html][http_haihongblog.com_archives_911.html]

下面是我的Java实现版本：

package com.phn.string;
    import java.util.Arrays;
    /**
     * @author 潘海南
     * @Email 1016593477@qq.com
     * @TODO 模式匹配算法
     * @date 2015年7月26日
     */
    public class FOKMP {
        
        private static int[] getNext(String Str) {
            int[] next = new int[Str.length()];
            int i, j;
            i = 0;
            j = -1;
            next[0] = -1;
            while (i < Str.length() - 1) {
                if (j == -1 || Str.charAt(i) == Str.charAt(j)) {
                    i++;
                    j++;
                    if (Str.charAt(i) != Str.charAt(j)) {
                        next[i] = j;
                    } else {
                        next[i] = next[j];
                    }
                } else {
                    j = next[j];
                }
            }
            return next;
        }
        public static int indexKMP(String S, String T) {
            int i = 0;
            int j = 0;
            int[] next = getNext(T);
            System.out.println(Arrays.toString(next));
            while (i <= S.length() - 1 && j <= T.length() - 1) {
                if (j == -1 || S.charAt(i) == T.charAt(j)) {
                    i++;
                    j++;
                } else {
                    j = next[j];
                }
            }
            if (j >= T.length())
                return i - T.length();
            return -1;
        }
    }

[http_study.163.com_course_courseMain.htm_courseId_468002]: http://study.163.com/course/courseMain.htm?courseId=468002
[http_www.ruanyifeng.com_blog_2013_05_Knuth_E2_80_93Morris_E2_80_93Pratt_algorithm.html]: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
[http_blog.csdn.net_v_july_v_article_details_7041827]: http://blog.csdn.net/v_july_v/article/details/7041827
[http_haihongblog.com_archives_911.html]: http://haihongblog.com/archives/911.html