两串旋转

亦凉 2022-06-09 01:12 135阅读 0赞

如果对于一个字符串A，将A的前面任意一部分挪到后边去形成的字符串称为A的旋转词。比如A=”12345”,A的旋转词有”12345”,”23451”,”34512”,”45123”和”51234”。对于两个字符串A和B，请判断A和B是否互为旋转词。

给定两个字符串A和B及他们的长度lena，lenb，请返回一个bool值，代表他们是否互为旋转词。

# 测试样例：
    "cdab",4,"abcd",4
    # 返回：true

> 参考文章：从头到尾彻底理解KMP [https://www.nowcoder.com/study/vod/1/1/4][https_www.nowcoder.com_study_vod_1_1_4]

**参考答案**

python版  
（只是不是到用 python in 来判断是否有匹配也可以，不是说好要KMP的吗？囧~）

# -*- coding:utf-8 -*-
    
    class Rotation:
        def chkRotation(self, A, lena, B, lenb):
            # write code here
            if lena != lenb:
                return False
            else:
                combineStr = A + A
                print combineStr
                if B in combineStr:
                    return True
                else:
                    return False

Java版

import java.util.*;
    
    public class Rotation { 
        public boolean chkRotation(String a, int lena, String b, int lenb) {
            if (a == null || b == null || lena != lenb) {
                return false;
            }
            String b2 = b + b;
            return getIndexOf(b2, a) != -1;
        }
    
        // KMP Algorithm
        public int getIndexOf(String s, String m) {
            if (s.length() < m.length()) {
                return -1;
            }
            char[] ss = s.toCharArray();
            char[] ms = m.toCharArray();
            int si = 0;
            int mi = 0;
            int[] next = getNextArray(ms);
            while (si < ss.length && mi < ms.length) {
                if (ss[si] == ms[mi]) {
                    si++;
                    mi++;
                } else if (next[mi] == -1) {
                    si++;
                } else {
                    mi = next[mi];
                }
            }
            return mi == ms.length ? si - mi : -1;
        }
    
        public int[] getNextArray(char[] ms) {
            if (ms.length == 1) {
                return new int[] { -1 };
            }
            int[] next = new int[ms.length];
            next[0] = -1;
            next[1] = 0;
            int pos = 2;
            int cn = 0;
            while (pos < next.length) {
                if (ms[pos - 1] == ms[cn]) {
                    next[pos++] = ++cn;
                } else if (cn > 0) {
                    cn = next[cn];
                } else {
                    next[pos++] = 0;
                }
            }
            return next;
        }
    }

[https_www.nowcoder.com_study_vod_1_1_4]: https://www.nowcoder.com/study/vod/1/1/4