在C中找到一個字符串中的子字符串C

給定一個字符串數組我試圖找到給定子字符串開始和結束的索引。這裏是我的代碼：在C中找到一個字符串中的子字符串C

#include <stdio.h> 

void find_sub_string(char *str, char *sub){ 
    int start= 0; 
    int end = 0; 
    int i=0,j=0; 

    while((str[i] != '\0')){ 

     if(str[i] == sub[j]){ 
      if(j == 0){ 
       start = i; 
      } 

      i++,j++; 

     } else if(str[i] != sub[j]){ 
      j=0; 
      if(str[i] == sub[j]){ 
       start = i; 
       j++,i++; 
      } else{ 
       i++; 
      } 
     } 

     if (sub[j] == '\0'){ 
      end = i-1; 
      printf("The start is: %d ,and end is : %d\n",start,end); 
      return; 
     } 
    } 

    printf("The substring %s was not found in string %s\n",sub,str); 
    return; 
} 


int main(){ 
    char str[] = "internet"; 
    char sub[] = "net"; 

    find_sub_string(str,sub); 

    return 0; 
}

我認爲，運行時間爲O（n），但我因爲else if語句可我不相信，我一直可以追溯到串的開頭（J = 0）每次我看到str [i]！= sub [j]。我擔心它可能會導致運行時間不是O（n）。

P.s這不是一個家庭作業問題。我只是在練習問題。

來源

2014-10-07 Wobblester

只有一個循環，它遍歷原始字符串。 'j'在這裏並不重要，因爲它不會影響循環的迭代次數。它是'O（n）'。 – 2014-10-07 19:07:21

如果你添加了'printf（「i =％dj =％d在行％d \ n」，i，j，__LINE __）;''給每個「then」和「else」分支，兩個內部* if-else *（所以將* else *添加到第一個）。 – hyde 2014-10-07 19:35:11

外循環將運行O（n）次，因爲i總是遞增一次，並受字符串大小的限制。在循環的每次迭代中完成的操作數是一個有界常量，因爲它中的每個語句最多可以運行一次，並且每個語句都執行固定的工作量。因此代碼是O（n）。

來源

2014-10-07 19:09:12

在C中找到一個字符串中的子字符串C

回答

相關問題