什么是下面算法的复杂性顺序查找给定字符串的子字符串

-1

我已经写下面的代码来查找给定的字符数组是否是主数组的子字符串。请说出以下代码的最佳情况和最坏情况的复杂顺序。什么是下面算法的复杂性顺序查找给定字符串的子字符串

我觉得这是非常有效的O（mainstring.lenth-substring.length）算法最复杂的算法。

public class SubstringOfString { 


    public static boolean isSubstring (char[] main , char[] sub){ 

     int base=0 ; 
     int i=0; 

     while(i<sub.length){ 
      if(sub[i]!=main[base] && i >0){ 
      base=base-i; 
       if (base>main.length-sub.length){ 
        System.out.println("not found"); 
        return false; 
       } 

      } 
      else { 
       i++;base++; 
      } 

     } 

     if (i==sub.length){ 
     System.out.println("found at"+(base-sub.length)); 
     return true; 
     } 
     return false; 

    } 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     char[] main = "i am hello as hello well".toCharArray(); 
     char[] sub="hello".toCharArray(); 
     SubstringOfString.isSubstring(main,sub); 

    } 

}

来源

2014-09-12 Mohit Gupta

我不这么认为，因为你可以给它两个非常长，相同的字符串。它仍然会检查这些字符串的每个字符。另外，这个算法不适用于main =“aaab”和sub =“aab”吗？ – guest 2014-09-12 20:41:16

[请参阅此处]（http://stackoverflow.com/questions/14615264/big-o-analysis-of-a-sub-string-of-string-algorithm-does-onlogn-simplify）与大O分析相关这个话题。我实际上并不相信你可以得到n的大O，除非在字符串中使用单个字符。 – Compass 2014-09-12 20:43:10

@guest这是否适用于main =“aaab”和sub =“aab” – 2014-09-12 21:10:58

最好的情况复杂度：O（substring.length）最佳案例：串发现在出发mainstring

最坏情况的复杂性：O（mainstring.length）最坏情况：在主串找到。 length-sub.length

来源

2014-09-12 20:43:37 G8XSU

再次考虑你的回应。 – 2014-09-12 20:44:09

首先，您当前的解决方案实际上并未按照您提供的示例运行：base很快变为负值。

其次，最差情况下的运行时间为（substring.length * mainstring.length），因为每次找到不匹配的字符时都必须将多个位置回溯到子字符串长度。

例如：

char[] main = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".toCharArray(); //60 A's 
char[] sub = "aaaaaaaaaaaaaaaB".toCharArray(); //15 A's 
isSubstring(main,sub); //compares each 'a' in main up to 15 times

来源

2014-09-12 21:49:52 Andreas

什么是下面算法的复杂性顺序查找给定字符串的子字符串

回答

相关问题