如何在C中遞歸地查找另一個字符串中的字符串位置？

Question

我們有一個任務，創建包含兩個字符串參數的遞歸功能，原型應該是這樣的：

int instring(char* word, char* sentence); 

如果我們將通話功能：

instring("Word", "Another Word"); 

它應該有以下返回值：

• 如果可以找到該單詞它將在
• 返回它會已經找到了字位置。如果是的話就不會被發現，它會返回-1

我可以用第三個參數，我保存的位置做到這一點，但不幸的是，我們不允許使用2個以上的參數。

所以問題是我如何得到它的工作？ 這是我想出了迄今：

int instring(char* word, char* sentence){ 
    if(*word == '\0') 
     return 0; 
    else if(*word != '\0' && *sentence == '\0') 
     return -1; 
    else 
     if(*word == *sentence) 
      instring(word+1, sentence+1); 
     else 
      instring(word, sentence+1); 
} 

我得到0，如果「字」，可以發現，否則我得-1。由於我無法在函數調用中存儲任何值，因此我無法獲取「單詞」字符串開始的位置。 除了外部變量和只有兩個輸入字符串，還有其他方式可以獲得位置嗎？

Answer 1

int instring(char* word, char* sentence){ 
    int lenw = strlen(word); 
    int lens = strlen(sentence); 
    if(lenw > lens) return -1; 

    if(strncmp(sentence, word, lenw)==0) 
     return 0; 
    else { 
     int ret = instring(word, sentence + 1); 
     if(ret < 0) 
      return ret; 
     return 1 + ret; 
    } 
} 

Answer 2

int len1 = strlen(word); 
int len2 = strlen(sentence); 
int n,k=0; 

for(int i =0;i<len2;i++){ 
n =i; 
    while(sentence[n] == word[k] && n<len2){ 
     if(k==len1 && (n==len2 || sentence[n+1] ==' ') 
     return i;//if word found return the position in the original string// 
     n++; 
     k++; 
} 
k =0; 
while(sentence[i] != ' ' && i<len2) //go to next word// 
i++; 
} 
return -1; 

Answer 3

我不認爲這些是特別優雅的解決方案，但隨後的問題也並不十分優雅（標準的解決方案是迭代和遞歸是不是最優的）。這是一個純粹的遞歸解決方案（不重複），這是相當低效：

#include <stdio.h> 

static int const debug = 0; 

static int instring(char const *word, char const *sentence) 
{ 
    int rc; 
    if (debug) 
    printf("-->> [%s] in [%s]\n", word, sentence); 
    if (*word == '\0') 
    rc = 0; 
    else if (*sentence == '\0') 
    rc = -1; 
    else if (*word != *sentence || (rc = instring(word+1, sentence+1)) != 0) 
    { 
    if ((rc = instring(word, sentence+1)) >= 0) 
     rc++; 
    } 
    if (debug) 
    printf("<<-- [%s] in [%s] = %d\n", word, sentence, rc); 
    return rc; 
} 

int main(void) 
{ 
    char word[] = "Word"; 
    char str1[] = "Another Word"; 
    char str2[] = "Wrong parts of the data"; 
    char str3[] = "A Word Or Two"; 

    printf("Search for [%s] in [%s] at offset %d\n", 
     word, str1, instring(word, str1)); 
    printf("Search for [%s] in [%s] at offset %d\n", 
     word, str2, instring(word, str2)); 
    printf("Search for [%s] in [%s] at offset %d\n", 
     word, str3, instring(word, str3)); 
    return 0; 
} 

如果設置debug = 1;你會看到爲什麼它是低效的。它使用變量rc來簡化調試跟蹤。

下面是一個更有效的替代方法，因爲它在第一個字符匹配時使用迭代來限制搜索。不難看出如何刪除剩餘的遞歸（這是簡單的尾遞歸），留下完全迭代的解決方案，這是解決此問題的常規方法。

#include <stdio.h> 

static int instring(char const *word, char const *sentence) 
{ 
    int rc; 
    if (*word == '\0') 
    return 0; 
    if (*sentence == '\0') 
    return -1; 
    if (*word == *sentence) 
    { 
    int i; 
    for (i = 1; word[i] != '\0' && word[i] == sentence[i]; i++) 
     ; 
    if (word[i] == '\0') 
     return 0; 
    } 
    if ((rc = instring(word, sentence+1)) >= 0) 
    rc++; 
    return rc; 
} 

int main(void) 
{ 
    char word[] = "Word"; 
    char str1[] = "Another Word"; 
    char str2[] = "Wrong parts of the data"; 
    char str3[] = "A Word Or Two"; 

    printf("Search for [%s] in [%s] at offset %d\n", 
     word, str1, instring(word, str1)); 
    printf("Search for [%s] in [%s] at offset %d\n", 
     word, str2, instring(word, str2)); 
    printf("Search for [%s] in [%s] at offset %d\n", 
     word, str3, instring(word, str3)); 
    return 0; 
} 

輸出示例：

Search for [Word] in [Another Word] at offset 8 
Search for [Word] in [Wrong parts of the data] at offset -1 
Search for [Word] in [A Word Or Two] at offset 2 

測試代碼可以在兩個版本（可以提高通過檢查結果的期望是什麼，以及通過使用測試功能，而不是寫了這麼多的代碼三次，也許通過循環來掃描測試數據。