0
  1. 我想知道这在最坏的情况下是否有效Θ(n+m)？

n是 的大小i_StringForSearch，m是 的大小i_SubStringToFind。

2.有没有推荐的程序来检查给定代码的时间复杂度，我更喜欢一个公认的免费工具。

谢谢

public static boolean isSubstring(String i_StringForSearch, String i_SubStringToFind)
    {
        int strForSearchIndex = 0;
        int subStrToFindIndex = 0;
        boolean endOfStringToSearch = false;
        boolean foundSubString = false;
        boolean isThereASequenceOfMatching = false;


        while(!endOfStringToSearch && !foundSubString)
        {
            if(strForSearchIndex == i_StringForSearch.length())
            {
                endOfStringToSearch = true;
            }

            else if(i_StringForSearch.charAt(strForSearchIndex) == i_SubStringToFind.charAt(subStrToFindIndex))
            {
                isThereASequenceOfMatching = true;
                if(subStrToFindIndex == i_SubStringToFind.length() -1 )
                {
                    foundSubString = true;
                }
                subStrToFindIndex++;
                strForSearchIndex++;
            }

            else if(i_StringForSearch.charAt(strForSearchIndex) != i_SubStringToFind.charAt(subStrToFindIndex))
            {
                if(isThereASequenceOfMatching)
                {
                    subStrToFindIndex = 0;
                    isThereASequenceOfMatching = false;
                }
                strForSearchIndex++;
            }
        }

       return foundSubString;
    }
4

1 回答 1

1

  1. 回答你的问题：是的，算法是O(n+m). 每次迭代都会增加strForSearchIndex，所以最多有n 迭代。[这是假设i_StringForSearch.length()在 中完成的O(1)，这通常是正确的]。

  2. 该算法与 的反例错误isSubstring("aaab","aab") == false。

  3. 您可能想看看Knuth Morris Pratt 算法和/或Rabin-Karp 算法和/或Aho-Corasick 算法

于 2012-09-04T10:52:43.367 回答