【C/C++刷题——leetcode】查找字符串中最大的子串

@TOC

---

前言

在字符串处理中，经常需要寻找一个字符串中的最大子串。最大子串指的是在给定字符串中连续出现的长度最长的子串。本文将介绍如何使用C++/C语言来查找一个字符串中的最大子串。

---

一、示例

输入:"Hello everybody"
输出:"everybody"

输入:"i am C++"
输出:"C++"

以空格分割每一个子字符串，遇到'\0'返回

二、要求分析

1、遍历字符串 对于此要求，我们肯定需要遍历整个字符串，才能求出他的最长字符串。 2、定义存储最长字符串的变量 定义存储上一个字符串的变量（如上面这个例子：我遍历到everybody了，那么上一个字符串就是Hello），定义存储现在的字符串（当遇到空格或者'\0'的时候自动给上一个字符串，并清空，好在下一次字符串使用）。创建后两个字符串的意义就是要比较得出最大字符串 3、如果无空格或'\0'，在存储现在字符串里面尾添加 4、如果有，则去判断上一个字符串和现在存储的字符串哪个大，从而得出maxStr。

三、C语言版

1、遍历字符串：

//由于strlen函数并不会加'\0'，可以'\0'也是我们的一个判断的一个标准
	//所以需要+1
	int len = strlen(str) + 1;

    for (int i = 0; i < len; i++) 
    {
        
    }

2、定义存储字符串的变量： 字符数组也可以增大，或者有能力的同学也可以使用malloc等等方法动态申请‘ 实现一个相对智能的函数

int maxLen = 0;              // 最大子串长度
    char maxStr[100];            // 存储最大子串的字符数组
    char lastStr[100];           // 存储上一个子串的字符数组
    char ret[100];               // 存储当前子串的字符数组

3、如果无空格或'\0'，在存储现在字符串里面尾添加：

ret[retLen++] = str[i];

4、如果有，则去判断上一个字符串和现在存储的字符串哪个大，从而得出maxStr。

if (strlen(lastStr) > maxLen) {
                strncpy(maxStr, lastStr, strlen(lastStr) + 1);
                maxLen = strlen(lastStr);
                retLen = 0;
            }
            else {
                strncpy(maxStr, ret, strlen(ret) + 1);
                strncpy(lastStr, ret, strlen(ret) + 1);
                maxLen = strlen(ret);
                retLen = 0;
            }

char* logestStr(const char* str) {
    int maxLen = 0;              // 最大子串长度
    char maxStr[100];            // 存储最大子串的字符数组
    char lastStr[100];           // 存储上一个子串的字符数组
    char ret[100];               // 存储当前子串的字符数组
    int retLen = 0;              // 当前子串的长度

    int len = strlen(str) + 1;

    for (int i = 0; i < len; i++) {
        if (str[i] == ' ' || str[i] == '\0') {
            if (strlen(lastStr) > maxLen) {
                strncpy(maxStr, lastStr, strlen(lastStr) + 1);
                maxLen = strlen(lastStr);
                retLen = 0;
            }
            else {
                strncpy(maxStr, ret, strlen(ret) + 1);
                strncpy(lastStr, ret, strlen(ret) + 1);
                maxLen = strlen(ret);
                retLen = 0;
            }

            continue;
        }
        else {
            ret[retLen++] = str[i];
        }
    }

    return maxStr;
}

四、C++版

1、遍历字符串：

//由于string::length()函数并不会加'\0'，可以'\0'也是我们的一个判断的一个标准
	//所以需要+1
	int len = str.length()+1;

    for(int i = 0;i<len;i++)
    {
    }

2、定义存储字符串的变量：

string ret;//记录这次的字符串
    string lastStr;//记录上次的字符串
    string maxStr;//最长的字符串，最后用于返回

3、如果无空格或'\0'，在存储现在字符串里面尾添加：

ret.append(1,str[i]);//尾添加字符串

4、如果有，则去判断上一个字符串和现在存储的字符串哪个大，从而得出maxStr。

if(lastStr.length() > ret.length())//上次的字符串比这次的大，maxstr赋值成上次的字符串
{
      maxStr = lastStr;
      ret = "";//存储现在字符串清空，好下次使用
}
else
{
      maxStr = ret;//最大的是此次字符串，赋值给maxstr
      lastStr = ret;//我们需要存储起lastStr好下次对比
      ret = "";//存储现在字符串清空，好下次使用
}

全部代码如下

string logestStr(const string &str)
{
    int Strcount = 0;
    string ret;//记录这次的字符串
    string lastStr;//记录上次的字符串
    string maxStr;//最长的字符串，最后用于返回
	
	//由于string::length()函数并不会加'\0'，可以'\0'也是我们的一个判断的一个标准
	//所以需要+1
    int len = str.length()+1;

    for(int i = 0;i<len;i++)
    {
        if(str[i] == ' ' || str[i]== '\0')//当遇到分隔符的时候
        {
            if(lastStr.length() > ret.length())//上次的字符串比这次的大，maxstr赋值成上次的字符串
            {
                maxStr = lastStr;
                ret = "";//存储现在字符串清空，好下次使用
            }
            else
            {
                maxStr = ret;//最大的是此次字符串，赋值给maxstr
                lastStr = ret;//我们需要存储起lastStr好下次对比
                ret = "";//存储现在字符串清空，好下次使用
            }

            continue;//执行下一次循环
        }
        else
        {
            ret.append(1,str[i]);//尾添加字符串
        }
    }

    return maxStr;
}

我们还可以实现他一个重载函数，以便char数组使用：

char *logestStr(const char *str)
{
    return const_cast<char*>(logestStr(string(str)).c_str());
}

重载函数代码分析： 由于logestStr(string).c_str()他的返回值是一个const char *，但是我们的返回值是char*，因为我们也不知道使用者是否会操作这个char*，所以我们不要写const char*。 所以我们就需要使用const_cast去除const属性，然后通过return返回就可以了

总结

通过以上代码，我们可以利用C++/C语言来查找一个字符串中的最大子串。这个函数的实现利用循环遍历字符串，通过比较字符的连续性来确定最大子串的位置和长度，并提取出最大子串作为结果。

总结一下，本文介绍了如何使用C++/C语言来查找一个字符串中的最大子串。通过编写一个辅助函数，我们能够方便地在程序中进行最大子串的查找，为字符串处理提供了便利。

【本文由：高防cdn http://www.558idc.com/gfcdn.html 复制请保留原URL】