js 이상 한 면접 문제 가 나 왔 습 니 다.

// KPM  
//         
function initTable( str ){
    let arr = str.split('');//     
    let table = [];

    //        

    //                
    function _getFitValue( partString ){
        let partFitValue = 0;
        let prefixArr = []; //     
        let suffixArr = []; //     

        //               
        function _getSameLength( arr1, arr2 ){
            for(let i of arr1){
                for(let j of arr2){
                    if(i==j){
                        console.log('    ', i)
                        return i.length;
                    }
                }
            }
            return 0;
        }
        //       
        if( partString.length > 2 ) {
            for ( let i = 1; i < partString.length ; i++ ) {
                let j = partString.length - i;
                prefixArr.push( partString.substr( 0, i ) );
                suffixArr.push( partString.substr( i, j ) );
            }
            console.log('prefixArr',prefixArr);
            console.log('suffixArr',suffixArr);
            partFitValue = _getSameLength( prefixArr, suffixArr );
            return partFitValue;

        } else {
            return partFitValue;
        }
    }
    for( let i = 0; i < arr.length; i++ ) {
        let testStr = str.substr(0,i+1);
        console.log('testStr', testStr)
        table[i] = _getFitValue( testStr );
    }
    return table;
};
let table = initTable('ABCDABD');
console.log('table', table);
// KMP         a         b       b     a            -1

function KMP(sourceStr, searchStr) {
    //     
    let part = initTable(searchStr);
    let sourceLength = sourceStr.length;
    let searchLength = searchStr.length;
    let result;
    let i = 0;
    let j = 0;

   for (; i < sourceStr.length; i++) { //     ，  

        //   
        for (j = 0; j < searchLength; j++) {
            //       
            if (searchStr.charAt(j) === sourceStr.charAt(i)) {
                //       
                if (j == searchLength - 1) {
                  result = i - j;
                  break;
                } else {
                  //      ，     ，i++           
                  i++;
                }
            } else {
              //       i     
              if (j > 1 && part[j - 1] > 0) {
                i += (i - j - part[j - 1]);
              } else {
                //    
                i = (i - j)
              }
              break;
            }
        }
        if (result || result === 0) {
          break;
        }
    }


    if (result || result == 0) {
      return result
    } else {
      return -1;
    }
}


let index = KMP('BBC ABCDAB ABCDABCDABDE','ABCDABD');

function replaceString( a, b, c ){
    while(true){
        let num = KMP( a, b );//       indexOf()                    
        if( num !== -1 ){
            let a_chars = a.split('');
            a = "";
            let count = 0;
            for ( let i = 0; i < a_chars.length; i++ ) {
                if( i >= num && (i < num + b.length)){
                    if( count === 0 ) {
                        a = a + c;
                    }
                    count++;
                } else {
                    a = a + a_chars[i];
                }
            }
        } else {
            return a;
        }
    }
}

//        ：          c   b               
replaceString('cccccc','c','bc');