/**
 * KMP算法求解str1是否包含str2，若包含，返回包含的起始位置，若不包含，返回-1；
 * @param str1
 * @param str2
 * @returns {number}
 * @constructor
 */
function KMP(str1, str2) {
   if (str1.length < 1 || str2.length < 1 || str1.length < str2.length) {
      return -1;
  }
  var arr1 = str1.split('');
  var arr2 = str2.split('');
  var i1 = 0; //str1配对索引
  var i2 = 0; //str2配对索引
  var next = getNextArray(arr2);
  while (i1 < str1.length && i2 < str2.length) {
     //i1字符与i2字符配对成功，继续配对下一个
     if (arr1[i1] === arr2[i2]) {
        i1++;
        i2++;
     //未配对成功，next数组中只有0位置为-1，所以配对str1下一位
     } else if (next[i2] === -1) {
        i1++;
     //未配对成功，str2的最大前缀下一个与i1配对
     } else {
        i2 = next[i2];
     }
  }
return i2 === str2.length ? i1 - i2 : -1;//i2到头相当于配对成功
}
/**
 * 求解啊arr2的next数组
 * @param arr2
 * @returns {Array}
 */
function getNextArray(arr2) {
  if (arr2.length === 1) {
     return [-1];
  }
  var next = new Array(arr2.length);
  next[0] = -1;
  next[1] = 0;
  var pos = 2; //str2索引
  var cn = 0;//比较位置为前一个数的next值
  while (pos < arr2.length) {
     //判断前一个数与比较位置最大前缀的后一个数是否相等
     if (arr2[pos - 1] === arr2[cn]) { 
       //相等时该点的next数值则为某个数的next数值+1，继续循环下一个数
       next[pos++] = ++cn; 
     //不相等时，取cn位置做为比较位置
     } else if (cn > 0) {
       cn = next[cn];
     //cn<0时，比较位置为0位置，则该点next值为0
     } else {
       next[pos++] = 0;
    }
  }
return next;
}
console.log(KMP('12341234a', '1234a'));//4

/**
 * 给定一个字符串str1，只能往str1的后面添加字符变成str2。
 * 要求1：str2必须包含两个str1，两个str1可以有重合，但是不能以同一个位置开头。
 * 要求2：str2尽量短。
 * 要求返回str2。
 * @param str1
 * @returns {string} 
 */
function kmpQuestion1(str1) {
  var next = new Array(str1.length+1);
  var pos = 2;
  var cn = 0;
  var arr1 = str1.split('');
  next[0] = -1;
  next[1] = 0;
  //求next数组
  while(pos<arr1.length+1){
    if(arr1[pos-1]===arr1[cn]){
      next[pos++]=++cn;
    }else if(cn>0){
      cn=next[cn];
    }else{
      next[pos++]=0;
    }
  }
return str1+str1.substring(cn);
}
console.log(kmpQuestion1('123123'));//123123123