以下代碼如何運行？

-2

以下代碼返回字符串s1中的第一個位置，其中字符串s2中的任何字符出現。它最糟糕的時間複雜度是O（m + n）。怎麼樣？以下代碼如何運行？

#include<stdio.h> 

int any(char *s1, char *s2) 
{ 

    char array[256]; 

    int i; 
    if (s1 == NULL) { 
     if (s2 == NULL) { 
      return(0); 
     } else { 
      return(-1); 
     } 
    } 

    for(i = 0; i < 256; i++) { 
     array[i] = 0; 
    } 

    while(*s2 != '\0') { 
     array[*s2] = 1; 
     s2++; 
    } 

    i = 0; 
    while(s1[i] != '\0') { 
     if (array[s1[i]] == 1) { 
      return(i); 
     } 
     i++; 
    } 
    return(-1); 
}

來源

2012-08-27 srijla

我不知道... –

你需要定義你的主要操作，我假設它是對數組元素的訪問。如果長度（s1）= m且長度（s2）= n，並且最糟糕的情況是您最終會遍歷s1的所有字符，那麼您最終會訪問m + n個陣列位置（至少n個，因爲您總是複製s2中的所有元素） – AlvaroGMJ

如果s2'爲NULL，但s1'不是，或者如果char有符號並且任何一個字符串都包含負的char，那麼該函數可能會突然中斷。 –

它分兩步進行。

它初始化大小爲256（代表每個的有效字符的輸入字符串）的陣列，以及用於在s2中每個字母（Ñ）標誌着字符點的陣列1中，以指示該角色存在。
它遍歷整個字符S1（0到米），在檢查陣列中的每個字符位置，看它是否被設置爲「存在」（1），其將指示它是在第二串。如果是，則返回s1中該字符的索引。如果s1中沒有任何字符存在於s2中（發現於m），則返回-1。

由於步驟1將始終以Ñ（S2的長度），和步驟2將需要最多米（s1的長度）時，最壞的情況是O（M + N），只有在沒有匹配時纔會發生，或者只有s1中的最後一個字符出現在s2中。

來源

2012-08-27 15:51:32 yoozer8

明白了。謝謝。非常好解釋...謝謝.... :-) – srijla

1件事情....這是什麼意思？ while（* s2！='\ 0'）array [* s2] = 1; s2 ++; } – srijla

以下代碼如何運行？

回答

相關問題