public class HelloWorld {
    public static void main(String[] args) {
        // char[] a = { '记','录','模','式','串','中','每','个','字','符','最','后','出','现','的','位','置' };      
        // char[] b = { '每','个','字'};

        char[] a = { 'I', 'L', 'o', 'v', 'e', 'C', 'o', 'd', 'e' };      
        char[] b = { 'd', 'e'};


        System.out.println("asccii  "+ (int)'式');
        System.out.println("char [] 长度" +a.length);
        int index = BM(a,a.length,b,b.length);
        System.out.println("查找到的位置在第 "+ index+" 个");

    }

    private static final int SIZE = 256; // 全局变量或成员变量

    // a,b表示主串和模式串；n，m表示主串和模式串的长度。
    public static int BM(char[] a,int n,char[] b,int m) {
        int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
        generateBC(b, m, bc); // 构建坏字符哈希表
        int[] suffix = new int[m];
        boolean[] prefix = new boolean[m];
        generateGS(b, m, suffix, prefix);
        int i = 0; // j表示主串与模式串匹配的第一个字符
        while (i <= n - m) {
            int j;
            for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
            if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是j
            }
            if (j < 0) {
            return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
            }
            int x = j - bc[(int)a[i+j]];
            int y = 0;
            if (j < m-1) { // 如果有好后缀的话
            y = moveByGS(j, m, suffix, prefix);
            }
            i = i + Math.max(x, y);
        }
        return -1;
    }

    //散列表,数组的下标对应字符的ASCII码值,数组中存储这个字符在模式串中出现的位置
    //注:如果模式串中出现相同的字符那就记录后面的
    /*                   模式串  a  b  d  a
    ASSCII表                     0  1  2  3 （模式串里出现了两个“a”,只会记录一个位置,后面出现的刷新前面的位置）
       a 97        bc: -1 -1 ... 3  1  -1   2 .... -1
       b 98            0  1 ... 97 98 99 100 .... 255
       c 99
       d 100
       .....*/

    //这里的hash算法太简单了,只适合用来匹配字母，如果需要匹配中文那就需要改进hash算法
    public static void generateBC(char[] b, int m, int[] bc) {
        for (int i = 0; i < SIZE; ++i) {
            bc[i] = -1; // 初始化bc
        }
        for (int i = 0; i < m; ++i) { // i递增,巧妙的将出现相同的字符时,后面的将前面的数值覆盖
            int ascii = (int)b[i]; // 计算b[i]的ASCII值
            bc[ascii] = i;
        }
    }

    /*suffix数组说明：表示模式串中后缀子串的长度,下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值。
        * * * * * * c a b * * * * *
                    ------(这是{u})
           模式串    c a b c a b
                    ------(这是{u*})
                    ↓ ↓ ↓
          起始下标值 0 1 2

        后缀子串  长度  suffix
              b    1   suffix[1] = 2
            a b    2   suffix[2] = 1
          c a b    3   suffix[3] = 0
        b c a b    4   suffix[4] = -1 (找不到就等于-1)
      a b c a b    5   suffix[5] = -1
    c a b c a b    6   suffix[6] = -1
    */

    // b表示模式串，m表示长度，suffix，prefix数组事先申请好了
    public static void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
        for (int i = 0; i < m; ++i) { // 初始化
            suffix[i] = -1;
            prefix[i] = false;
        }
        for (int i = 0; i < m - 1; ++i) { // b[0, i]
            int j = i;
            int k = 0; // 公共后缀子串长度
            while (j >= 0 && b[j] == b[m-1-k]) { // 与b[0, m-1]求公共后缀子串
            --j;
            ++k;
            suffix[k] = j+1; //j+1表示公共后缀子串在b[0, i]中的起始下标
            }
            if (j == -1) prefix[k] = true; //如果公共后缀子串也是模式串的前缀子串
        }
    }

    // j表示坏字符对应的模式串中的字符下标; m表示模式串长度
    public static int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
        int k = m - 1 - j; // 好后缀长度
        if (suffix[k] != -1) return j - suffix[k] +1;
            for (int r = j+2; r <= m-1; ++r) {
                if (prefix[m-r] == true) {
                return r;
                }
            }
            return m;
    }
}

// 转为字符串比较
var isPalindrome1 = function(x) {
    if ( x < 0 ) return false
    let str = '' + x
    return Array.from(str).reverse().join('') === str
};

// console.log(isPalindrome1(12321))
// console.log(isPalindrome1(12345654321))

// 数学方法
/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if(x < 0 || (x%10==0 && x!==0)) return false;
    var revertedNum = 0; 
    while(x>revertedNum){
        revertedNum = revertedNum*10 + x%10;
        x = Math.floor(x /= 10);
    }
    
    return Math.floor(revertedNum/10) === x || revertedNum === x

};

//是回文数
console.log("121——" + isPalindrome(121))
console.log("12345654321——" + isPalindrome(12345654321))
console.log("11——" + isPalindrome(11))
console.log("12321——" + isPalindrome(12321))
console.log("0——" + isPalindrome(0))
console.log("1——" + isPalindrome(1))
console.log("\n")
//不是回文数
console.log("-121——" + isPalindrome(-121))
console.log("10——" + isPalindrome(10))
console.log("NaN——" + isPalindrome(NaN))
console.log("\n")
//疑惑的情况。。。
console.log("+0——" + isPalindrome(+0))
console.log("-0——" + isPalindrome(-0))
console.log("+1——" + isPalindrome(+1))