当前位置：首页 > article >正文

算法刷题[比较两个字符串的最大公字符串（滑动窗口实现）]

article 2024/9/27 12:08:49

题目：编程实现：找出两个字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串为"cad"

代码如下所示：

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* 
   编程实现：找出两个字符串中最大公共子字符串,
   如"abccade","dgcadde"的最大子串为"cad" 
 */

/* 采用滑动窗口的算法实现 */
bool fun(char* str1, char* str2, char* ret)
{
	if ((NULL == str1) || (NULL == str2) || (NULL == ret)) return false;
	int maxlen=0, startindex = 0, retlen = 0;
	int len1 = strlen(str1), len2 = strlen(str2);
	for (int i = 0; i < len1; i++)          //str1字符串的遍历
	{
		for (int j = 0; j < len2; j++)      //str2字符串的遍历
		{
			retlen = 0;
			/* 如果首字母相等，进行滑动窗口的比较 */
			while ((i + retlen < len1) && (j + retlen < len2) && (str1[i + retlen] == str2[j + retlen]))
				retlen++;
			if (maxlen < retlen)      //记录相同字符串最长的长度、起始索引地址。
			{
				maxlen = retlen;
				startindex = i;
			}
		}
	}
	if (maxlen > 0)
	{
		strncpy(ret, &str1[startindex], maxlen);
		ret[maxlen] = '\0';
	}else
		ret[maxlen] = '\0';
	return true;
}


int main()
{
	char str1[] = "abdcaddec";
	char str2[] = "dgcadde";
	char ret[10];
	fun(str1, str2, ret);
	printf("str:%s\r\n", ret);
	return 0;
}

运行结果如下所示：