9.20字节跳动前端笔试第五场

第一题，生兔子问题。使用动态规划，斐波那契就可以得到，核心代码：

var rabbit = [1,1]
for(let i=2;i<=month;i++){
    rabbit[i] = rabbit[i-1] + rabbit[i-2]
}
return rabbit[month]

var myTest = function (str) {
    const len = str.length;
    for (let t = 1; t <= len / 2; t++) {
        // 从零开始  一个一个进行截取
        const item = str.slice(0, t);
        // 算出重复多少次才能够得到原本的字符串
        const count = len / item.length;
        if (Number.isInteger(count) && item.repeat(count) === str) {
            return item
        }
    }
    // 未找到 返回
    return str
}

自测，一万长度的字符串可以输出，耗时0.168s。但题目好像要求的是字符串长度最大1e8,求大佬给个KMP求解的题解。

对于快速幂计算，没写出来。