KMP算法与Manacher算法

本文主要是介绍KMP算法与Manacher算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

KMP算法

KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字（接下来称它为P），如果它在一个主串（接下来称为T）中出现，就返回它的具体位置，否则返回-1（常用手段）。例如str= "abctabcf" match="tab" 返回3，在str中包含match字符串的开头位置

图解：

代码：

    public static int getIndexOf(String s1, String s2) {
        if (s1 == null || s2 == null || s2.length() < 1 || s1.length() < s2.length()) {
            return -1;
        }
        char[] str = s1.toCharArray();
        char[] match = s2.toCharArray();
        int x = 0;//str中当前比对到的位置
        int y = 0;//match中当前比对到的位置
        // O(M) m <= n，next[i]:在match中i之前的字符串match[0...i-1]前缀后缀相等的最大长度
        int[] next = getNextArray(match);
        // O(N)
        while (x < str.length && y < match.length) {
            if (str[x] == match[y]) {
                x++;
                y++;
            } else if (next[y] == -1) { // next[y] == -1:y == 0
                x++;
            } else {
                y = next[y];//假设在12位置的指标为5，则前五个数为0，1，2，3，4，直接跳到5
            }
        }
        //1. x越界，y没越界，-1， 2.x没越界，y越界，说明str中某个位置可以把match包含，找到str中匹配到的开头x-y,栗子str=aabcaabf,match=aabf  3.都越界，str=aab,m=aab
        return y == match.length ? x - y : -1;
    }
    
    
     //match的各个指标  O(M)，指标：该字符之前的字符串前缀与后缀相等的最大长度
    public static int[] getNextArray(char[] match) {
        if (match.length == 1) {
            return new int[] { -1 };
        }
        int[] next = new int[match.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2; // 目前在哪个位置上求next数组的值
        // cn位置的字符代表当前是哪个位置的值在和i-1位置的字符比较，既是i-1情况下的指标也是前缀与后缀相等的最大长度的下一个字符的下标
        int cn = 0; 
        while (i < next.length) {    
            if (match[i - 1] == match[cn]) { // 配成功的时候
                next[i] = cn +1;
                i ++;
                cn ++;
                //三句合并一句 next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];//匹配失败再往前跳
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }

Manacher算法

Manacher算法是一个用来查找一个字符串中的最长回文子串(不是最长回文序列)的线性算法。它的优点就是把时间复杂度为O(N^2)的暴力算法优化到了O(n)。

需要理解的基本概念：

str = #f#1#a#1#s#

回文半径：4

回文直径：7

回文半径数组pArr[]: #1#2#2#1# ---->[1,3,1,7,1,3,1]

代码：

//求一个字符串中最长回文字串
    public static int manacher(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // "12132" -> "#1#2#1#3#2#"
        char[] str = manacherString(s);
        // 回文半径数组
        int[] pArr = new int[str.length];
        int C = -1;
        // 讲述：R代表最右的扩成功的位置
        // coding：最右的扩成功位置的，再下一个位置
        int R = -1;
        //回文数组中的最大值，如果是回文直径则/2,如果是回文半径则-1
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < str.length; i++) { // 0 1 2
            /*
             * 四种情况：
             * 1.i在R外  暴力解 自己不需要验，是1
             * 2.i在R内  找到最小值就是不用验的区域
             * 2.1 i对应的i'的回文区域在[L..R]内  prr[i'] 直接拿答案
             * 2.2 i对应的i'的回文区域在[L..R]外  i到R距离 直接拿答案R-i
             * 2.3 i对应的i'的回文区域在的左边界与L重合  R-i
             */
            
            // R第一个违规的位置，R > i--> i>= R :i在R外，不用验，是1
            // i位置扩出来的答案，i位置扩的区域，至少是多大。
            //2 * C - i：i的对称点i'，i到R的距离与i'的回文半径谁小谁就是i的回文半径
            
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
                
            //右侧不越界，左侧不越界，看能不能往外扩，情况1跟4可以扩，情况2跟3只要进while就会退出
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                //i + pArr[i]:i加上不用验的区域，往俩测扩，如果相等，回文半径加1
                if (str[i + pArr[i]] == str[i - pArr[i]])
                    pArr[i]++;
                else {
                    break;
                }
            }
            
            //i位置扩完之后看看能不能更新R与C
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            
            max = Math.max(max, pArr[i]);
        }
        //"121"-->"#1#2#1#"  manacher对应的回文半径-1就是原字符串的回文区域---> 4-1=3
        return max - 1;
    }
    
    //“121121”------>“#1#2#1#1#2#1#”
    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

栗子：

给定一个字符串str，只能在str后面添加字符使之整体变成回文字符串，返回需要添加的字符串。例如""abcd123321"",返回"dcba"

代码：

    //abcd123321--->返回后面添加的dcba
    public static String shortestEnd(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        char[] str = manacherString(s);
        int[] pArr = new int[str.length];
        int C = -1;
        int R = -1;
        //包含最后一个字符的最长回文字串的回文半径
        int maxContainsEnd = -1;
        for (int i = 0; i != str.length; i++) {
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                if (str[i + pArr[i]] == str[i - pArr[i]])
                    pArr[i]++;
                else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            //一旦发现到了最后一个位置，跳出来，记录maxContainsEnd
            if (R == str.length) {
                maxContainsEnd = pArr[i];
                break;
            }
        }
        //s=abc12321 str=#a#b#c#1#2#3#2#1# 最大回文半径maxContainsEnd=6,原始包含最后一个字符的最长回文字符串长度6-1=5，需要补的长度8-6+1=3
        char[] res = new char[s.length() - maxContainsEnd + 1];
        //把s前面的字符依次逆序添加到后面 
        for (int i = 0; i < res.length; i++) {
            res[res.length - 1 - i] = str[i * 2 + 1];
        }
        return String.valueOf(res);
    }

  //“121121”------>“#1#2#1#1#2#1#”
    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

这篇关于KMP算法与Manacher算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！