字符串移位包含问题_JAVA_编程开发_程序员俱乐部

问题：给定两个字符串s1和s2，要求判断s2是否能够通过s1做循环移位操作得到的字符串包含。例如，给定s1＝AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD，返回false。

答：这个问题可以使用“提高空间复杂度来换取时间复杂度的降低”的思路来解决。

实现代码：

public class ShiftStringMatch {
        public static final int MATCH = 1;
        public static final int NOMATCH = 0;

        private String source;

        public ShiftStringMatch(String source){
                this.source = source;
        }

        public int doMatch(String pattern) {
                String str = this.source + this.source;
                if(str.contains(pattern)){
                        return MATCH;
                }else{
                        return NOMATCH;
                }
        }

        public static void main(String[] args){
                String s1="AABCD";
                String s2="CDAA";
                ShiftStringMatch ssm = new ShiftStringMatch(s1);
                if(ssm.doMatch(s2)==ShiftStringMatch.MATCH){
                        System.out.println("Contain!");
                }else{
                        System.out.println("Not Contain!");
                }
        }
}