求两个字符串的最大公共子串 - 黑马程序员技术交流社区

//
// main.c
// 第二题
// 找出多个字符串中的最大公共子字符串，如“nbitheimanb”和“itheia”的最大子串是：”ithei”。（C语言）
// Created by 张立鹏 on 16/4/15.
// Copyright © 2016年 0323Basic. All rights reserved.
//
#include <stdio.h>
#include <string.h>
#define GETSUBSTR (str1[i+k] == str2[j+k] && str1[i+k] != '\0' &&str2[j+k] != '\0')
int main(int argc, const char * argv[]) {
char str1[] = "myloveisxiaoyu";
char str2[] = "alcobvceaivsmamaaoyuloveisxiaoyu";
size_t lenStr1 = strlen(str1);
size_t lenStr2 = strlen(str2);
void getMaxSubString(char* str1,char* str2,size_t lenStr1,size_t lenStr2);
getMaxSubString(str1, str2, lenStr1, lenStr2);
return 0;
}
/**
* @author 0323Basic, 16-04-15 19:04:52
*
* 找出两个字符串之中的公共子串
* 思路:
* 遍历结束条件遇到'\0'
* 两个字符串比较时,先找到两个字符串中相同的元素,
* 从这个元素起遍历后面的字符,比较字符是否相同
* 判断条件:
* 比较的字符不应该是'\0'
* 若依然有相同的字符则记录起始字符的位置和起始字符后相同的字符数
* 根据需求最终要求得最大子串
* 所以当起始位置后相同的字符数大于上一次的记录
* 那么覆盖上次记录
* 最后根据记录的起始遍历位置和长度输出公共字串
*
* @param str1 字符串1
* @param str2 字符串2
* @param lenStr1 字符串1的长度
* @param lenStr2 字符串2的长度
*/
void getMaxSubString(char* str1,char* str2,size_t lenStr1,size_t lenStr2){
int index = 0; //记录子串起始位置
int count = 0; //记录子串起始位置之后的长度
for (int i = 0; str1[i] != '\0'; i++) {
for (int j = 0; str2[j] != '\0'; j++) {
if (str1[i] == str2[j]) {
for (int k = 1; GETSUBSTR; k++) {
if (k>count) {
index = i;
count = k;
}
}
}
}
}
for (int i = 0; i<=count; i++) {
printf("%c",str1[index+i]);
}
printf("\n");
}

复制代码