编程之美-字符串移位包含的问题

ゝ一世哀愁。 2022-08-04 12:48 158阅读 0赞

第三章　3.1　字符串移位包含的问题

问题详细描述:

给定两个字符串s1和s2，要求判断s2是否能够被s1做循环移位得到的字符串包含。

输入输出示例：

给定s1=”AABCD”和s2=”CDAA”，返回true；

给定s1=”ABCD”和s2=”ACBD”，返回false。

对于编程之美中使用C语言的解法请参见这一篇文章，讲的很详细  
地址：[字符串移位包含的问题 - 丫坏孩子 - 博客园][- _ -]

下面是我的Java版本的解法，其中用到了KMP模式匹配算法，不懂的可以去看看我之前的一篇,  
地址：[Java数据结构-串及其应用-KMP模式匹配算法 | Pan Hai nan’Blog][Java_-_-KMP_ _ Pan Hai nan_Blog]  
里面推荐了怎么学习KMP模式匹配算法。

下面贴上我的代码：`StringRotate.java`

package com.chapter.third;
    /**
     * @author phn
     * @TODO 字符串移位包含的问题
     * 问题详细描述:
     *    给定两个字符串s1和s2，要求判断s2是否能够被s1做循环移位得到的字符串包含。
     * 输入输出示例：
     *    给定s1="AABCD"和s2="CDAA"，返回true；
     *    给定s1="ABCD"和s2="ACBD"，返回false。
     */
    public class StringRotate {
        /**
         * @TODO 蛮力法解题：通过对s1循环移位，直接进行判断
         * @param srcChar
         * @param desChar
         * @return true or false
         */
        public static boolean rotate0(char []srcChar,char []desChar){
            for(int i=0;i<srcChar.length;i++){
                //这里调用KMP模式匹配算法进行判断是否包含问题
                //返回-1表示不包含，返回其他表示包含且首地址为返回值。
                if(FOKMP.indexKMP(srcChar, desChar)!=-1){
                    return true;
                }
                char tempChar = srcChar[0];
                //这里做循环移位
                for(int j = 0;j<srcChar.length-1;j++){
                    srcChar[j] = srcChar[j+1];
                }
                srcChar[srcChar.length-1] = tempChar;
            }
            return false;
        }
        /**
         * @TODO 通过将s1转化为s1s1，判断s1s1是否包含s2来得出问题的解（空间换时间）
         * @param srcChar
         * @param desChar
         * @return true or false
         */
        public static boolean rotate1(char []srcChar,char []desChar){
            char []doubleSrcChar = new char[2*srcChar.length];
            //将两个srcChar连接变成doubleSrcChar
            for(int i = 0; i<2*srcChar.length; i++){
                doubleSrcChar[i] = srcChar[i%srcChar.length];
            }
            //这里调用KMP模式匹配算法进行判断是否包含问题
            //返回-1表示不包含，返回其他表示包含且首地址为返回值。
            if(FOKMP.indexKMP(doubleSrcChar, desChar)!=-1){
                return true;
            }
            return false;
        }
    
    }

辅助类KMP模式匹配算法：`FOKMP.java`

package com.chapter.third;
    /**
     * @author 潘海南
     * @Email 1016593477@qq.com
     * @TODO 模式匹配算法
     */
    public class FOKMP {
        private static int[] getNext(char []Str) {
            int[] next = new int[Str.length];
            int i, j;
            i = 0;
            j = -1;
            next[0] = -1;
            while (i < Str.length - 1) {
                if (j == -1 || Str[i] == Str[j]) {
                    i++;
                    j++;
                    if (Str[i] != Str[j]) {
                        next[i] = j;
                    } else {
                        next[i] = next[j];
                    }
                } else {
                    j = next[j];
                }
            }
            return next;
        }
        public static int indexKMP(char []S, char []T) {
            int i = 0;
            int j = 0;
            int[] next = getNext(T);
            while (i <= S.length - 1 && j <= T.length - 1) {
                if (j == -1 || S[i] == T[j]) {
                    i++;
                    j++;
                } else {
                    j = next[j];
                }
            }
            if (j >= T.length)
                return i - T.length;
            return -1;
        }
    }

测试方法：

public static void main(String[] args) {
        System.out.println("rotate0:"+rotate0("ABCD".toCharArray(),"ACBD".toCharArray()));
        System.out.println("rotate1:"+rotate1("ABCD".toCharArray(),"ACBD".toCharArray()));
        System.out.println("rotate0:"+rotate0("AABCD".toCharArray(),"CDAA".toCharArray()));
        System.out.println("rotate1:"+rotate1("AABCD".toCharArray(),"CDAA".toCharArray()));
    }

[- _ -]: http://www.cnblogs.com/sooner/p/3270548.html
[Java_-_-KMP_ _ Pan Hai nan_Blog]: http://panhainan.com/2015/08/23/Java%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E4%B8%B2%E5%8F%8A%E5%85%B6%E5%BA%94%E7%94%A8-KMP%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95/

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关字符串移位包含问题

include <stdio.h> include <stdlib.h> include <string.h> int main(int arg

小灰灰/ 2022年12月11日 13:50/ 0 赞/ 107 阅读

相关字符串是否包含问题

题目描述假设这有两个分别由字母组成的字符串A另外字符串B，字符串B的字母数较字符串A少一些。什么方法能最快地查出字符串B所有字母是不是都在字符串A里？也就是说判断字符串

柔光的暖阳◎/ 2022年08月27日 05:50/ 0 赞/ 235 阅读

相关字符串移位包含的问题——解题笔记

字符串移位包含的问题——解题笔记题目描述：给定两个字符串s1和s2，要求判定s2时候能够被s1做循环移位（rotate）得到的字符串包含。例如，给定s1=AAB

墨蓝/ 2022年08月06日 17:10/ 0 赞/ 145 阅读

相关编程之美-字符串移位包含的问题

第三章　3.1　字符串移位包含的问题问题详细描述: 给定两个字符串s1和s2，要求判断s2是否能够被s1做循环移位得到的字符串包含。输入输出示例：给定s1

ゝ一世哀愁。/ 2022年08月04日 12:48/ 0 赞/ 159 阅读

相关字符串移位包含的问题

问题：给定两个字符串s1和s2，要求判断s2是否能够被通过s1做循环移位（rotate）得到的字符串包含。例如，S1=AABCD和s2=CDAA，返回true；给定s1=ABC

清疚/ 2022年07月18日 01:12/ 0 赞/ 129 阅读

相关 java字符串包含问题

/ 用于判断用逗号分隔的字符串测试第一个字符串是否包含第二个字符串的内容若不包含则返回第一个不包含的内容

素颜马尾好姑娘i/ 2022年06月13日 01:22/ 0 赞/ 237 阅读

相关【算法】字符串循环移位后是否包含

问题 > 给定两个字符串s1和s2，要求判断s2是否能够被通过s1做循环移位（rotate）得到的字符串包含。 > 例如，s1=AABCD和s2=CDAA，返回tru

偏执的太偏执、/ 2022年06月02日 02:43/ 0 赞/ 186 阅读

相关计算字符串的相似度--编程之美3.3

许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：　　1.修改一个字符（如

清疚/ 2022年05月24日 12:08/ 0 赞/ 210 阅读

相关字符串移位包含问题研究

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

痛定思痛。/ 2022年05月15日 01:35/ 0 赞/ 182 阅读

相关【编程之美】字符串移位包含的问题

问题描述：给定两个字符串s1和s2，要求判定s2是否能被s1循环移位（rotate）得到的字符串包含。例如，给定字符串s1=AABCD和s2=CDAA，返回true；给定s

妖狐艹你老母/ 2022年04月24日 15:28/ 0 赞/ 185 阅读