时间戳

首页 > 解决方案 > 在C ++中递归搜索char数组子字符串中第一次出现的char数组子字符串

c++ - 在C ++中递归搜索char数组子字符串中第一次出现的char数组子字符串

问题描述

我正在尝试递归搜索字符数组以查找由另一个字符数组组成的序列的第一次出现。我不允许使用字符串、预定义的字符串函数或循环。我正在搜索的字符数组是程序中使用的名称，并且此函数用于另一个函数中，该函数要求用户输入输入的子字符串，然后它在程序中搜索 5 个名称以查找任何具有完全匹配的名称的子字符串输入。我不能在这里发布其余的代码。目前，我的程序总是告诉我，无论我输入什么，都找不到名字。

bool IsSubString(char name[], char search_str[], int i, int found_flag, int idx)
{
if (name[i] != '\0' && search_str[idx] != '\0')
    {
        if (search_str[idx] == name[i])
        {
            if (idx == 0)
            {
                found_flag = 1;
            }
            else
            {
                found_flag = found_flag * 1;
            }
            idx++;
        }
        else
        {
            found_flag = 0;
            idx = 0;
        }
        i++;
        IsSubString(name, search_str, i, found_flag, idx);
    }
    

    if (search_str[idx] == '\0')
        return found_flag;
    else
        return false;
}

标签： c++arraysrecursionsearchchar

解决方案

我发现很难准确理解您的要求，但据我了解，这里有两种解决方案，

如果你想检查 name[] == search_str[] ：

bool IsEqual(char name[], char search_str[], int i)
{
    if (name[i] == '\0' && search_str[i] == '\0')
        return true;
    if (search_str[i] != name[i])
        return false;

    return IsEqual(name, search_str, ++i) 
}

如果要获取给定字符串中第一次出现子字符串的索引：

/*
    str[] - The string to search in.
    search[] - The substring to search for.
    
    Returns -1 if substring not found.
*/
int getIndex(char str[], char search[], int index, int i,int j)
{
    if( search[j] == '\0' )
        return index;       // Substring found.
    if( str[i] == '\0' )
        return -1; // Search string ended but substring not found.

    if( str[i] == search[j] )
    {
        if( j == 0 ) index = i; // Sets index equal to the index of first charector of search in str 
        j++; ​
    ​}
    else 
    {
        index = -1; // Sets index back to -1 due to missmatched charector.
        j = 0;
    }
    
    return getIndex(str[], search[], index, ++i, j) // Continue search.
}

要使用该功能，

getIndex(char_array_to_search, search_string, -1, 0 , 0);

例如 ，

printf("%d",getIndex("the main string", "main", -1,0,0)); // prints 4
printf("%d",getIndex("one and one", "one", -1,0,0)); // prints 0
printf("%d",getIndex("one and one", "one", -1,1,0)); // prints 8
printf("%d",getIndex("nospace", "nos", -1,0,0)); // prints 0

您必须为 index 传递 -1，为 j 传递 0。如果您为 i 传递任何大于 0 的数字，则搜索将从该索引开始。

如果您只想知道子字符串是否存在，

bool found = getIndex(str, search, -1, 0,0) != -1;

只是为了好玩，这里有一个压缩得多的版本，也许是为了给你的老师留下深刻印象：

int getIndex(char str[], char search[], int index, int i,int j)
{
    if( search[j] == '\0' )
        return index;       // Substring found.
    if( str[i] == '\0' )
        return -1; // Search string ended but substring not found.

    index =  (j==0) * ((str[i] == search[j]) * (i + 1) - 1)  + (j!=0) * index;
    j += (str[i] == search[j]) - (str[i] != search[j])*j;
    
    return getIndex(str[], search[], index, ++i, j) // Continue search.
}

推荐阅读