C语言 查找两个字符串中的最大公共子串,三种方法实现
时间: 2023-05-18 16:05:51 浏览: 178
1. 暴力枚举法:对于两个字符串中的每一个子串,判断是否在另一个字符串中出现,时间复杂度为O(n^3)。
2. 动态规划法:定义一个二维数组dp[i][j]表示以第一个字符串中第i个字符和第二个字符串中第j个字符结尾的最长公共子串的长度,然后根据状态转移方程dp[i][j] = dp[i-1][j-1] + 1或者dp[i][j] = 0,时间复杂度为O(n^2)。
3. 后缀数组法:将两个字符串拼接起来,中间用一个特殊字符隔开,然后求出后缀数组和height数组,height[i]表示排名为i和i-1的后缀的最长公共前缀的长度,然后找到height数组中的最大值即可,时间复杂度为O(nlogn)。
相关问题
C语言查找两个字符串中的最大公共子串
可以使用动态规划算法来查找两个字符串中的最大公共子串。具体步骤如下:
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. 在遍历的过程中,记录下最长的公共子串的长度和结束位置。
5. 根据结束位置和最长公共子串的长度,可以得到最长公共子串。
以下是示例代码:
```c
#include <stdio.h>
#include <string.h>
void findLCS(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;
}
} else {
dp[i][j] = 0;
}
}
}
if (maxLen == 0) {
printf("没有找到公共子串\n");
} else {
printf("最长公共子串为:");
for (int i = endPos - maxLen; i < endPos; i++) {
printf("%c", str1[i]);
}
printf("\n");
}
}
int main()
{
char str1[] = "abcdefg";
char str2[] = "bcdehij";
findLCS(str1, str2);
return 0;
}
```
输出结果为:
```
最长公共子串为:bcde
```
C语言实现查找两个字符串中的最大公共子串
可以使用动态规划算法来实现查找两个字符串中的最大公共子串。具体实现方法如下:
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".
```