C++:求两个字符串的最大公有子串和字符串逆序

淡淡的烟草味﹌ 2022-05-26 05:19 171阅读 0赞

#include "iostream"
    using namespace std;
    
    
    #include<cassert>
    #include <string>
    //找出两个字符串中最长的公共子串（如果存在多个 ， 返回第一个）
    //参数：str1　　 字符串1
    //　　　str2     字符串2
    //　　　maxSubStr 　　 找到的最大子串
    void findMaxSubstr(const char * str1, const char * str2, char * maxSubstr){
    	assert((str1 != NULL) && (str2 != NULL));
    	assert(maxSubstr != NULL);
    	int maxPos = -1;
    	int maxLen = 0,k;
    	for (int i = 0; i<strlen(str1); i++){
    		for (int j = 0; j<strlen(str2); j++){
    			if (str1[i] == str2[j]){
    				for (k = 1; (str1[i + k] == str2[j + k]) && (str1[i + k] != '\0'); k++);
    				if (k>maxLen){
    					maxPos = i;
    					maxLen = k;
    				}
    			}
    		}
    	}
    	if (maxPos == -1){
    		maxSubstr[0] = '\0';
    	}
    	else{
    		memcpy(maxSubstr, str1 + maxPos, maxLen);
    		maxSubstr[maxLen] = '\0';
    	}
    }
    
    //方法2
    char* lcs(char *str1, char *str2)
    {
    	int len1, len2;
    	int i, j;
    	char *shorter, *longer, *substr;
    	if (str1 == NULL || str2 == NULL)return NULL;
    
    	len1 = strlen(str1);
    	len2 = strlen(str2);
    
    	if (len1 < len2)
    	{
    		shorter = str1;
    		longer = str2;
    	}
    	else
    	{
    		shorter = str2;
    		longer = str1;
    	}
    
    	if (strstr(longer, shorter) != NULL) return shorter;
    
    	len1 = strlen(shorter);
    	substr = (char*)malloc(len1 + 1);
    
    	for (i = len1 - 1; i > 0; i--)
    	{
    		for (j = 0; j <= len1 - i; j++)
    		{
    			memcpy(substr, &shorter[j], i);
    			substr[i] = '\0';
    			if (strstr(longer, substr) != NULL) return substr;
    
    		}
    	}
    
    	return NULL;
    
    
    }
    
    
    //方法3
    string lcs_search(string str1, string str2)//求两个字符串的公共子串  
    {
    	int len1 = str1.length();
    	int len2 = str2.length();
    	int length = 0;
    	int end = 0;
    	if (len1 < len2)
    	{
    		string temp = str1;
    		str1 = str2;
    		str2 = temp;
    		len1 = str1.length();
    		len2 = str2.length();
    	}
    	int *sign = new int[len1];
    	for (int i = 0; i < len2; i++)
    	{
    		for (int j = len1 - 1; j >= 0; j--)
    		{
    			if (str2[i] == str1[j])
    			{
    				if (i == 0 || j == 0)sign[j] = 1;
    				else sign[j] = sign[j - 1] + 1;
    			}
    			else sign[j] = 0;
    			if (sign[j] > length)
    			{
    				length = sign[j];
    				end = j;
    			}
    		}
    	}
    	delete[]sign;
    	return str1.substr(end - length + 1, length);
    
    }
    
    
    //方法4
    string   FindMAxSubString(string a, string b)
    {
    	string res = "";
    	string shorter = a.length()>b.length() ? b : a;
    	string longer = a.length()>b.length() ? a : b;
    
    	int maxlen = 0;
    	int maxpos = -1;
    	for (int i = 0; i<shorter.length(); i++){
    		for (int j = 0; j<longer.length(); j++)
    		{
    			if (shorter[i] == longer[j])
    			{
    				int k = 1;
    				for (; (shorter[i + k] == longer[j + k]) && i + k<shorter.length(); k++);
    				if (k>maxlen){
    					maxpos = i;
    					maxlen = k;
    				}
    			}
    		}
    	}
    
    	if (maxpos == -1)
    		return res;
    	else
    	{
    		res = shorter.substr(maxpos, maxlen);
    		return res;
    	}
    
    }
    
    int main(){
    
    	char substr[20];
    
    	findMaxSubstr("zhangligu", "gligzhangligu", substr);
    	//cout << lcs("zhangligu", "gligzhangligu");
    	//cout << lcs_search("zhangligu", "gligzhangligu");
    	cout << FindMAxSubString("zhangligu", "gligzhangligu");
    	
    	//cout << substr << endl;
    
    	return 0;
    
    }

字符串逆序

char* str_reverse(char* str)
    {
    	int n = strlen(str) / 2;
    	int i = 0;
    	char tmp = 0;
    
    	for (i = 0; i < n; i++)
    	{
    		tmp = str[i];
    		str[i] = str[strlen(str) - i - 1];
    		str[strlen(str) - i - 1] = tmp;
    	}
    
    	return str;
    }

部分内容参考自：[点击打开链接1][1][点击打开链接2][2][点击打开链接3][3]

[1]: http://blog.sina.com.cn/s/blog_4ff373440100vuq4.html
[2]: https://www.cnblogs.com/deanlan/p/4751087.html
[3]: https://blog.csdn.net/u011484045/article/details/48344695