给出两个字符串,求最长的相同子串的C语言实现
时间: 2023-02-08 08:28:22 浏览: 81
下面是求最长公共子串的C语言代码实现:
```
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int longestCommonSubstring(char *s1, char *s2) {
int m = strlen(s1);
int n = strlen(s2);
int maxLength = 0;
int end = 0;
int dp[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 0;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
end = i - 1;
}
} else {
dp[i][j] = 0;
}
}
}
// return the longest common substring
if (maxLength > 0) {
char result[maxLength + 1];
for (int i = end - maxLength + 1; i <= end; i++) {
result[i - (end - maxLength + 1)] = s1[i];
}
result[maxLength] = '\0';
printf("Longest common substring: %s\n", result);
}
return maxLength;
}
int main() {
char s1[100], s2[100];
printf("Enter the first string: ");
scanf("%s", s1);
printf("Enter the second string: ");
scanf("%s", s2);
printf("Length of the longest common substring: %d\n", longestCommonSubstring(s1, s2));
return 0;
}
```
这段代码使用了动态规划算法。算法原理就是通过比较两个字符串中对应位置的字符是否相同来更新 dp 数组。最后通过求 dp 数组中最大值来求出最长公共子串。