还是把这道kmp的题po出来吧，省的以后自己也忘了

做了一个问题突然想到可以用Kmp解决，所以看了一下自己之前写的关于Kmp的博客用JAVA实现的KMP匹配子串，记录一下，省的又忘了。

/*
*题目描述:
* 假定我们都知道非常高效的算法来检查一个单词是否为其他字符串的子串。
* 请将这个算法编写成一个函数，给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成，要求只能调用一次检查子串的函数。
* 给定两个字符串s1,s2,请返回bool值代表s2是否由s1旋转而成。
* 字符串中字符为英文字母和空格，区分大小写，字符串长度小于等于1000。
*/

/*
*解题思路:
*
*方案1：
*分别比较字符串的原串和旋转串的前半段和旋转部分的后半段，两段都相同即返回true.
*时间复杂度为O(n2)
*
*方案2:
*假设原字符串有ABCD四个部分，旋转子串则有BCDA->CDAB->DABC->ABCD四种这四种都是ABCDABCD的子串，
*所以就将原问题转化为了判断新串是否是原串+原串的子串的问题.
*可以采用系统自带的contains函数或者kmp算法解决匹配子串的问题.
*/
解决代码如下：

public int[] getNext(String str)

    {

        if(str == null || str.length() == 0)

        {

            return null;

        }

        int strLen = str.length();

        int next[] = new int[strLen+1]; //next数组表示，长度为i的字符串最长公共前后缀的长度为next[i]，所以需要多一个空间

        next[0] = next[1] = 0;

        int j;

        for(int i = 1; i < strLen; i++)

        {

            j = next[i];

            if(str.charAt(i) == str.charAt(j))

            {

                next[i+1] = next[i] + 1; //直接找到不用计算

            }

            else

            {//继续寻找next[next[i]]

                while(j > 0 && str.charAt(i) != str.charAt(j))

                {

                    j = next[j]; //递归查找next[]，直到找到字符相等或next[1];

                }

                if(str.charAt(i) == str.charAt(j))

                {

                    next[i+1] = next[j] + 1; //next

                }

                else

                {

                    next[i+1] = 0;

                }

            }

        }

        return next;

    }

    public boolean findsubString(String originStr,String findStr,int next[])

    {

        if(originStr == null || findStr == null || originStr.length() == 0 || findStr.length() == 0)

        {

            return false;

        }

        int matchLen = 0; //上一次已匹配的长度

        for(int i = 0; i < originStr.length(); i++)

        {

            if(originStr.charAt(i) == findStr.charAt(matchLen))

            {

                matchLen++;

                if(matchLen == findStr.length())

                {//找到子串

                    return true;

                }

            }

            else

            {//通过next数组计算出findStr跳转的位置

                while(matchLen > 0 && originStr.charAt(i) != findStr.charAt(matchLen))

                {

                    matchLen = next[matchLen];

                }

            }

        }

        return false;

    }

    public boolean checkReverseEqual(String s1, String s2)

    {

        if(s1 == null || s2 == null)

        {

            return false;

        }

        int oldLen = s1.length(),newLen = s2.length();

        if(oldLen != newLen)

        {

            return false;

        }

        String s3 = s1 + s1;

        int next[] = getNext(s2);

        return findsubString(s3,s2,next);

        /*

         方法2

        String s3 = s1 + s1;

        return s3.contains(s2);

        */

        /*

         方法3

        int oldIndex;

        boolean flag = true;

        for(int i = 0; i < oldLen; i++)

        {

            oldIndex = i;

            flag = true;

            if(s1.charAt(i) == s2.charAt(0))

            {

                //比较旋转的前半段

                int newIndex;

                for(newIndex = 0; oldIndex + newIndex < oldLen; newIndex++)

                {

                    if(s1.charAt(oldIndex + newIndex) != s2.charAt(newIndex))

                    {

                        flag = false;

                        break;

                    }

                }

                if(flag == true)

                {

                    //比较旋转的后半段

                    for(int k = 0; k < oldIndex; k++)

                    {

                        if(s1.charAt(k) != s2.charAt(newIndex + k))

                        {//newIndex + k防止新串不偏移

                            flag = false;

                            break;

                        }

                    }

                }

                if(flag == true)

                {

                    return true;

                }

            }

        }

        */

    }

巴特西

还是把这道kmp的题po出来吧，省的以后自己也忘了

最新文章

热门文章