使用遞歸計算較大陣列中的子陣列的出現次數

Question

我必須編寫一個遞歸函數來計算較大陣列s1中存在的短陣列s2的次數，而不會重疊。我可以使用多個可以幫助我的函數，但它們必須是遞歸函數。例如：

#define n 10 
#define p 2 

s1[n]={0,2,3,23,54,1,8,23,54,1} 
s2[p]={23,54} 
OUTPUT: 2 (we see s2 two times in s1) 

我想過寫一個遞歸函數，它告訴我，如果有則至少有一個occurence在計數出現次數的數量與另一遞歸函數使用此功能。所以這是我寫的：

//Initially pos1=0 and pos2=0 

int find(int *s1,int *s2,int pos1,int pos2){ 
if(n-pos1<p-pos2) 
    return 0; 

if(*(s1+pos1)==*(s2+pos2)){ 
    if(pos2==p-1) 
     return pos1; 
    else{ 
     if(find(s1,s2,pos1+1,pos2+1)) 
      return pos1; 
    } 
} 
return find(s1,s2,pos1+1,0); 
} 

然後我寫了一個應該算OCCURENCES數量第二遞歸函數：

// Initially occ(s1,s2,0); 
int occ(int *s1,int *s2,int memo){ 
    if(memo==n){ //end of s1 
     return 0; 
    } 
    else{ 
     if(find(s1+memo,s2,memo,0)) 
    return 1+occ(s1+memo,s2,memo+p); 
    } 
} 

它背後的想法是，以驗證是否存在至少如果發生了一次，則計數並重新驗證s1的剩餘部分直到結束。

問題是，第二個函數的代碼根本不起作用，我無法找到修復它的方法。

那麼如何編寫第二個遞歸函數，使用上面寫的函數find（）計算出現次數？

Answer 1

從OP's comment

它的工作原理，如果s1[n]={0,0,0,3,4,0,0,0,3,4,0,0,0,3,4,0,0,0,3,4};和s2[p]={3,4}。事實上，輸出是4.但是，如果s2[p]={0,0}輸出是0這是不正確的。

• 這是因爲，當s2={0,0}的find()函數返回pos1 = 0作爲所述子集存在於一開始因而在occ()功能如果（找到（S1 +備忘錄，S2，備忘錄，0） ）的計算結果爲是虛假並結束函數不返回任何值，並且這個調用未定義的行爲

• 這可以通過返回一個可以避免y的數字不是0，但它不能是陣列中的任何有效位置值s1。

• 由於位置不能負號，我選擇-1

---

請看下面的代碼就知道如何避免它：

#include <stdio.h> 

#define n 10 
#define p 2 

int s1[n]={0,2,3,23,54,1,8,23,54,1}; 
int s2[p]={23,54}; 

//find function 
int find(int* s1,int* s2,int pos) //only used `pos` instead of `pos1`, removed `pos2` 
{ 
    if(pos > n-2) 
    { 
     return -1; //returns `-1` upon reaching the end of the code 
    } 

    if(*(s1+pos) == *(s2+0)) //check at `s1+pos` 
    { 
     if(*(s1+(pos+1)) == *(s2+1)) //check next element `s1+pos+1` 
     { 
      return pos; //if both true return `pos` 
     } 

     else 
     { 
      return find(s1,s2,pos+1); //else recursively find in the rest of the array 
     } 
    } 

    return find(s1,s2,pos+1); // recursively find in the rest of the array 
} 


//occurence function  
int occ(int *s1, int *s2,int memo) 
{ 
    if(memo == -1) //if end of the array, end adding occurrences by returning 0 
    { 
     return 0; 
    } 

    else 
    { 
     memo = find(s1, s2, memo); //scan position into memo 

     if(memo != -1) //if not end of the array i.e, `-1` add to occurrence 
     { 
      return 1+occ(s1,s2,memo+2); 
     } 

     else 
     { 
      return 0; //else return 0 and recursion would end in next call as memo is -1 
     } 
    } 
} 

//main function 
int main(void) 
{ 
    printf("%d",occ(s1,s2,0)); //just to see the output 
} 

• 輸出：

  2 //true as {23,54} occur two times 
  

• 當輸入是：（編譯時間）

  #define n 20 
  #define p 2 
  
  s1[n]={0,0,0,3,4,0,0,0,3,4,0,0,0,3,4,0,0,0,3,4}; 
  s2[p]={0,0}; 
  

• 輸出：

  4 //true as {0,0} occurs at 0,5,10,16 
  

---