C语言输入2个字符,要求输出最长的公共子串

时间: 2023-10-09 09:08:51 浏览: 98
以下是使用暴力法(Brute-Force)求解最长公共子串的C语言代码: ```c #include <stdio.h> #include <string.h> int main() { char str1[100], str2[100]; printf("请输入两个字符串:\n"); scanf("%s%s", str1, str2); int len1 = strlen(str1), len2 = strlen(str2); int max_len = 0, max_i = -1, max_j = -1; for (int i = 0; i < len1; i++) { for (int j = 0; j < len2; j++) { int k = 0; while (str1[i+k] == str2[j+k] && i+k < len1 && j+k < len2) { k++; } if (k > max_len) { max_len = k; max_i = i; max_j = j; } } } if (max_len == 0) { printf("没有公共子串。\n"); } else { printf("最长公共子串为:"); for (int i = 0; i < max_len; i++) { printf("%c", str1[max_i+i]); } printf("\n"); } return 0; } ``` 这里使用两层循环枚举所有可能的子串,然后再用一个while循环找到最长的公共子串。时间复杂度为O(n^3),对于较长的字符串会比较慢。 如果需要更快的算法,可以考虑使用动态规划(Dynamic Programming)或后缀数组(Suffix Array)等方法。

相关推荐

最长的公共子串可以通过动态规划的方法来实现。我们可以定义一个二维数组dp[m][n],其中m和n分别表示字符串1和字符串2的长度。 首先,我们需要初始化第一行和第一列。如果字符串1的第i个字符和字符串2的第j个字符相同,就将dp[i][j]设为1,否则设为0。 然后,我们可以遍历整个二维数组,通过比较字符串1的第i个字符和字符串2的第j个字符是否相同,从而进行状态转移。如果相同,就将dp[i][j]设为dp[i-1][j-1]+1,表示以字符串1的第i个字符和字符串2的第j个字符结尾的最长公共子串的长度。 遍历结束后,我们可以找到最长的公共子串的长度。要找到具体的最长公共子串,我们可以记录最长公共子串的长度对应的索引位置,然后通过字符串切片的方法获取最长公共子串。 下面是该算法的示例代码: c #include <stdio.h> #include <string.h> void findLongestCommonSubstring(char* str1, char* str2) { int len1 = strlen(str1); int len2 = strlen(str2); int dp[len1+1][len2+1]; int max_len = 0; int end_index = 0; // 初始化第一行和第一列 for(int i = 0; i <= len1; i++) dp[i][0] = 0; for(int j = 0; j <= len2; j++) dp[0][j] = 0; // 动态规划求解 for(int i = 1; i <= len1; i++) { for(int j = 1; j <= len2; j++) { if(str1[i-1] == str2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; if(dp[i][j] > max_len) { max_len = dp[i][j]; end_index = i - 1; } } else dp[i][j] = 0; } } // 获取最长公共子串 char longest_substr[max_len+1]; strncpy(longest_substr, &str1[end_index-max_len+1], max_len); longest_substr[max_len] = '\0'; printf("最长的公共子串为:%s\n", longest_substr); } int main() { char str1[100]; char str2[100]; printf("请输入字符串1:"); scanf("%s", str1); printf("请输入字符串2:"); scanf("%s", str2); findLongestCommonSubstring(str1, str2); return 0; } 以上代码中,我们定义了一个函数findLongestCommonSubstring来实现计算最长公共子串的功能。在main函数中,我们分别输入两个字符串,并调用findLongestCommonSubstring函数来输出最长公共子串。
要输入两个字符的连续公共子串,我们可以使用C语言来实现。首先,我们需要定义两个字符串变量input1和input2用于接收输入的两个字符串。然后,我们可以先遍历其中一个字符串,记录下当前位置开始的子串长度,同时检查另一个字符串是否包含该子串。如果包含,则继续比较后续字符,直到遇到不匹配或遍历完其中一个字符串为止。最后,我们可以打印出找到的连续公共子串。下面是一个示例代码: c #include <stdio.h> #include <string.h> #define MAX_LENGTH 100 int main() { char input1[MAX_LENGTH]; char input2[MAX_LENGTH]; int maxLength = 0; int startIdx = -1; printf("请输入第一个字符串:"); scanf("%s", input1); printf("请输入第二个字符串:"); scanf("%s", input2); int len1 = strlen(input1); int len2 = strlen(input2); for (int i = 0; i < len1; i++) { int length = 0; int idx1 = i; int idx2 = 0; while(idx1 < len1 && idx2 < len2 && input1[idx1] == input2[idx2]) { length++; idx1++; idx2++; } if (length > maxLength) { maxLength = length; startIdx = i; } } if (maxLength > 0) { printf("连续公共子串为:"); for (int i = startIdx; i < startIdx + maxLength; i++) { printf("%c", input1[i]); } printf("\n"); } else { printf("没有连续公共子串。\n"); } return 0; } 你可以运行上述代码,并按照提示输入两个字符串,在计算完成后会输出连续公共子串。如果没有连续公共子串,则会显示相应的提示信息。
最长公共子串是指两个字符串中最长的相同部分,可以用动态规划的方法来求解。首先,我们可以定义一个二维数组来存储两个字符串中每个位置的公共子串的长度,然后利用动态规划的思想逐步填充数组。 首先,我们定义一个二维数组dp,dp[i][j]表示以字符串1的第i个字符和字符串2的第j个字符结尾的公共子串的长度。然后可以用以下动态规划的方法来填充dp数组: 如果字符串1的第i个字符和字符串2的第j个字符相等,那么dp[i][j] = dp[i-1][j-1] + 1 如果字符串1的第i个字符和字符串2的第j个字符不相等,那么dp[i][j] = 0 最后,我们可以在填充dp数组的过程中记录最长的公共子串的长度以及它在两个字符串中的位置,最后输出这个最长公共子串。 下面是c语言代码示例: c #include <stdio.h> #include <string.h> void longestCommonSubstring(char* str1, char* str2) { int len1 = strlen(str1); int len2 = strlen(str2); int dp[len1+1][len2+1]; int maxLen = 0; int endPos = 0; memset(dp, 0, sizeof(dp)); for(int i = 1; i <= len1; i++) { for(int j = 1; j <= len2; j++) { if(str1[i-1] == str2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; if(dp[i][j] > maxLen) { maxLen = dp[i][j]; endPos = i-1; } } } } if(maxLen == 0) { printf("No common substring found.\n"); } else { printf("The longest common substring is: "); for(int i = endPos - maxLen + 1; i <= endPos; i++) { printf("%c", str1[i]); } printf("\n"); } } int main() { char str1[] = "abcdefg"; char str2[] = "cdefg"; longestCommonSubstring(str1, str2); return 0; } 通过上面的c语言代码示例,我们可以输出最长公共子串,对于输入的两个字符串"abcdefg"和"cdefg",最长公共子串为"cdefg"。
C语言中实现动态规划的最长公共子串算法可以通过以下步骤来实现: 1. 定义一个二维数组dp[m+1][n+1],其中m和n分别为两个字符串的长度。 2. 初始化数组dp的第一行和第一列为0,即dp[i] = dp[j] = 0。 3. 使用两个循环遍历字符串的每个字符,i从1到m,j从1到n。 4. 如果两个字符相等,即str1[i-1] == str2[j-1],则dp[i][j] = dp[i-1][j-1] + 1。 5. 如果两个字符不相等,即str1[i-1] != str2[j-1],则dp[i][j] = 0。 6. 在循环过程中,记录最大的dp[i][j]值,以及对应的i和j的位置。 7. 循环结束后,最大的dp[i][j]就是最长公共子串的长度。 8. 可以根据最长公共子串的长度和i、j的位置,来获取最长公共子串的具体内容。 以下是一个示例代码: c #include <stdio.h> #include <string.h> void longestCommonSubstring(char* str1, char* str2) { int m = strlen(str1); int n = strlen(str2); int dp[m+1][n+1]; int maxLen = 0; int maxEndIndex = 0; // 初始化dp数组 for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { dp[i][j] = 0; } } // 计算dp数组 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (str1[i-1] == str2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; if (dp[i][j] > maxLen) { maxLen = dp[i][j]; maxEndIndex = i - 1; } } else { dp[i][j] = 0; } } } // 获取最长公共子串 char longestSubstring[maxLen + 1]; strncpy(longestSubstring, &str1[maxEndIndex - maxLen + 1], maxLen); longestSubstring[maxLen] = '\0'; printf("最长公共子串: %s\n", longestSubstring); } int main() { char str1[] = "abcdefg"; char str2[] = "cdefgh"; longestCommonSubstring(str1, str2); return 0; } 这段代码会输出最长公共子串:"cdef"。你可以根据需要修改字符串的内容进行测试。
可以使用动态规划算法来实现查找两个字符串中的最大公共子串。具体实现方法如下: 1. 定义一个二维数组dp,其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最大公共子串的长度。 2. 初始化dp数组,将所有元素都赋值为0。 3. 遍历两个字符串,如果第一个字符串的第i个字符和第二个字符串的第j个字符相等,则dp[i][j] = dp[i-1][j-1] + 1,否则dp[i][j] = 0。 4. 在遍历的过程中,记录最大的dp[i][j]的值以及对应的i和j,即为最大公共子串的长度和结束位置。 5. 最后根据最大公共子串的长度和结束位置,可以得到最大公共子串的起始位置和内容。 下面是C语言的实现代码: c #include <stdio.h> #include <string.h> void findMaxCommonSubstr(char* str1, char* str2) { int len1 = strlen(str1); int len2 = strlen(str2); int dp[len1+1][len2+1]; int maxLen = 0, endPos = 0; memset(dp, 0, sizeof(dp)); for(int i=1; i<=len1; i++) { for(int j=1; j<=len2; j++) { if(str1[i-1] == str2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; if(dp[i][j] > maxLen) { maxLen = dp[i][j]; endPos = i-1; } } else { dp[i][j] = 0; } } } if(maxLen == 0) { printf("No common substring found.\n"); } else { printf("The maximum common substring is \"%.*s\".\n", maxLen, str1+endPos-maxLen+1); } } int main() { char str1[] = "abcdefg"; char str2[] = "bcdehij"; findMaxCommonSubstr(str1, str2); return 0; } 输出结果为: The maximum common substring is "bcde".

最新推荐

C语言实现输入一个字符串后打印出该字符串中字符的所有排列

主要介绍了C语言实现输入一个字符串后打印出该字符串中字符的所有排列的方法,是数学中非常实用的排列算法,需要的朋友可以参考下

C语言实现将字符串转换为数字的方法

主要介绍了C语言实现将字符串转换为数字的方法,涉及系统函数atoi()函数的使用技巧,需要的朋友可以参考下

ssm数据结构课程网络学习平台的+vue毕业论文.doc

ssm数据结构课程网络学习平台的+vue毕业论文.doc

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire

Objective-C中的协议与代理设计模式介绍

# 1. 理解Objective-C中的协议 协议是Objective-C中一种很重要的特性,它类似于其他编程语言中的接口,用来定义对象之间的通信规则和行为约定。在Objective-C中,协议可以帮助实现对象之间的松耦合和重用性。让我们深入了解Objective-C中的协议。 ## 1.1 什么是Objective-C中的协议? 在Objective-C中,协议是一组方法的声明,定义了一个对象可以遵循的接口。协议本身并不实现任何方法,而是规定遵循该协议的类需要实现协议中定义的方法。通过协议,可以在不同的类之间定义一组公共的行为和方法。 ## 1.2 协议的声明和使用方法 在Ob

编写求n!的函数f(int n),在主函数中输入两个整数m、n,然后调用函数求: C=m!/n!(m -n)!

好的,我可以编写这个函数。以下是代码示例: ```c++ #include <iostream> using namespace std; int f(int n) { if (n <= 1) { return 1; } else { return n * f(n - 1); } } int main() { int m, n; cout << "请输入两个整数m和n,以空格分隔:" << endl; cin >> m >> n; int C = f(m) / (f(n) * f(m - n));

视频中运动目标跟踪算法的研究.doc

视频中运动目标跟踪算法的研究.doc

"互动学习:行动中的多样性与论文攻读经历"

多样性她- 事实上SCI NCES你的时间表ECOLEDO C Tora SC和NCESPOUR l’Ingén学习互动,互动学习以行动为中心的强化学习学会互动,互动学习,以行动为中心的强化学习计算机科学博士论文于2021年9月28日在Villeneuve d'Asq公开支持马修·瑟林评审团主席法布里斯·勒菲弗尔阿维尼翁大学教授论文指导奥利维尔·皮耶昆谷歌研究教授:智囊团论文联合主任菲利普·普雷教授,大学。里尔/CRISTAL/因里亚报告员奥利维耶·西格德索邦大学报告员卢多维奇·德诺耶教授,Facebook /索邦大学审查员越南圣迈IMT Atlantic高级讲师邀请弗洛里安·斯特鲁布博士,Deepmind对于那些及时看到自己错误的人...3谢谢你首先,我要感谢我的两位博士生导师Olivier和Philippe。奥利维尔,"站在巨人的肩膀上"这句话对你来说完全有意义了。从科学上讲,你知道在这篇论文的(许多)错误中,你是我可以依

Objective-C中的推送通知与APNs实现

# 1. 推送通知简介 推送通知是移动应用开发中常用的一种技术,它可以向用户发送消息、提醒或通知,即使用户并未在使用应用时也能及时获取重要信息。在Objective-C中,实现推送通知需要使用苹果提供的苹果推送通知服务(APNs)。本章将介绍推送通知的基础知识,包括推送通知的概念、作用和原理。接下来我们将深入了解。 ### 1.1 什么是推送通知 推送通知是通过网络将消息发送到设备的一种技术。应用程序可以向设备发送推送通知,无论用户当前是否在使用该应用,都可以及时获取到消息或通知。用户收到推送通知后,可以通过通知中的内容了解到消息的来源和内容,以便及时处理。 ### 1.2 推送通知的

php中,跳转语句有break和contimue

其实,`break`和`continue`并不是跳转语句,它们是用于控制循环语句的关键字。 `break`用于中断循环,跳出当前循环结构(如`for`、`while`、`do-while`),执行循环结构后面的语句。如果`break`语句后面跟着一个数字n,则表示跳出第n层循环。例如: ``` for ($i = 0; $i < 10; $i++) { for ($j = 0; $j < 10; $j++) { if ($j == 5) { break 2; // 跳出两层循环 } } } ``` `continue