旋转字符串

2019, Aug 10 mannuan One min read

题目描述

给字符串定义一个“旋转“的操作，比如字符串AbcD旋转一次变成bcDA。继续旋转则依次变成cDAb、DAbc、Abcd。给定两个字符串“源和目标”请判断“源“在旋转一定次数后，是否可以包含“目标

输入描述

三组长度非空字符串，一共6行，奇数行为“源“字符串，偶数行为“目标”字符串

输出描述

每组字符串是否可以旋转包含。包含返回 1, 不包含返回 0

示例1

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

AABCD
CDAA
AABCD
ABCD
AABCD
CFS

输出

110

代码待验证

function getPrefix(pattern, prefix){
    let i = 1;
    let len = 0;
    prefix[0] = 0;
    while(i<pattern.length){
        if(pattern[i] == pattern[len]){
            prefix[i++] = ++len;
        }else{
            if(len>0){
                len = prefix[len-1];
            }else{
                prefix[i++] = len;
            }
        }
    }
}
function kmpSearch(text, pattern){
    let prefix = [];
    getPrefix(pattern, prefix);
    prefix.unshift(-1);
    prefix.pop();
    let i = 0;
    let j = 0;
    while(i<text.length){
        if(text[i] == pattern[j] && j == pattern.length - 1){
            return i-j;
        }
        else if(text[i] == pattern[j]){
            i++;
            j++;
        }else{
            if(j==-1){
                i++;
            }else{
                j = prefix[j];
            }
        }
    }
    return -1;
}

function kmp(text, pattern){
    for(let i=0; i<text.length; i++){
        text = text.slice(1)+text[0];
        let res = kmpSearch(text, pattern);
        if(res>=0){
            return 1;
        }
    }
    return 0;
}

let text = "AABCD";
let patterns = ["CDAA", "ABCD", "CFS"];
patterns.forEach(e=>{
    console.log(kmp(text, e));
});