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 に答える