分享下"找出多个字符串中的最大公共子字符串"的一种写法 - 黑马程序员技术交流社区

//
// main.m
// 测试题10
//
// Created by 林柯 on 15/4/16.
// Copyright (c) 2015年 itcast. All rights reserved.
//
/*
10、找出多个字符串中的最大公共子字符串，如“nbitheimanb”和“itheia”的最大子串是：”ithei”。（C语言）
设计思路:
先判断哪个字符串的字符长度较短,假设为str1,在该字符串上建立循环,从第一个字符(i=0)开始
该字符在另一个字符串(假设为str2)中第一次出现的位置,若没有找到,则跳到str1的第二个字符(i=1)开始
若找到,则定位str2中该字符的位置(str2+j),开始依次判断接下来的字符是否相等,若相等将length的值+1
直到不相等为止,将最终的length与maxLength相比,若length>maxLength,maxLength=length;并储存字符字串
接着继续从str2+j开始继续查找是否有与str+i相同的字符……直到字符串末尾
接着将i的值+1,继续上述步骤;最后输出储存的字符串
获取三个字符串的最大公共字串
设计思路:
和设计获取两个字符串的最大公共字串的流程大致一样
从最短的字符串开始开始进行循环,但在第二个字符串中找到相同字符时不直接进行length的计算,
而是开始在第三个字符串中进行检索,找到相同字符再进行length的计算
以此类推可以写出N个字符串中的最大公共字串
*/
#include <stdio.h>
#include <string.h>
/**
* 查找两个字符串中的最大字串
*
* @param sameStr 用来储存最大字串的字符数组的指针地址
* @param str1 用来比较的字符串1
* @param str2 用来比较的字符串2
*/
void findSameInTwoStr(char *sameStr,char *str1,char *str2);
/**
* 查找三个字符串中的最大字串
*
* @param sameStr 用来储存最大字串的字符数组的指针地址
* @param str1 用来比较的字符串1
* @param str2 用来比较的字符串2
* @param str3 用来比较的字符串3
*/
void findSameInThreeStr(char *sameStr,char *str1,char *str2,char *str3);
int main(void)
{
//定义用来测试的字符串
char *str1 = "nbitheimanb";
char *str2 = "itheianb";
char *str3 = "foianb";
//定义一个字符数组,存储两个字符串中的最大字串
char sameStr[80];
findSameInTwoStr(sameStr,str1, str2);
//定义一个字符数组,存储三个字符串中的最大字串
char sameStr2[80];
findSameInThreeStr(sameStr2, str1, str2, str3);
//打印测试结果
printf("%s\n%s\n",sameStr,sameStr2);
return 0;
}
void findSameInThreeStr(char *sameStr,char *str1,char *str2,char *str3)
{
/*利用字符指针数组将str1,str2,str3的指针
以其所指向字符串长度从小到大重新分配给str1,str2,str3*/
char *str[3] = {str1,str2,str3};
for (int i = 0; i < 2; i++) {
for (int j = i+1; j < 3; j++) {
if (strlen(str[i]) > strlen(str[j])) {
char *temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}
}
str1 = str[0];
str2 = str[1];
str3 = str[2];
//定义int型变量,用来储存字串长度,最长字串长度
int length = 0,maxLength = 0;
//从str1中第一个字符开始,寻找str2中该字符的位置
for (int i = 0;i < strlen(str1);i++) {
for (int j = 0; j < strlen(str2); j++) {
//如果找到相同的字符,则在str3中寻找该字符
if (*(str1+i) == *(str2+j)){
for (int k = 0; k < strlen(str3); k++) {
//如果在三个字符串中都找到该字符,则开始计算相同字串长度
if (*(str1+i) == *(str2+j) && *(str1+i) == *(str3+k)) {
length = 0;
while (*(str1+i+length) == *(str2+j+length) && *(str1+i+length) == *(str3+k+length)) {
length++;
}
}
//若字串长度大于历史最长长度,则覆盖历史最长长度,并储存字符字串
if (length>maxLength) {
maxLength = length;
for (int count = 0; count < length; count++) {
*(sameStr+count) = *(str1+i+count);
}
}
}
}
}
}
}
void findSameInTwoStr(char *sameStr,char *str1,char *str2)
{
//获取str1指针指向最短的字符串,str2指向较长的字符串
if (strlen(str1) > strlen(str2)) {
char *temp = str1;
str1 = str2;
str2 = temp;
}
//定义int型变量,用来储存字串长度,最长字串长度
int length = 0,maxLength = 0;
/*取出str1+i对应的字符,在str2中寻找,若找到,其地址为str2+j
此时将使用一个while循环求出该字串的长度,之后将该长度与历史最长长度对比
若该长度较长,覆盖历史最长长度,保存该字符串,再进行下一次检索
直到str1的字符都取完为止*/
for (int i = 0; i < strlen(str1); i++) {
for (int j = 0; j < strlen(str2); j++) {
if (*(str1+i) == *(str2+j)) {
length = 0;
while (*(str1+i+length) == *(str2+j+length)) {
length++;
}
}
if (length>maxLength) {
maxLength = length;
for (int count = 0; count < length; count++) {
*(sameStr+count) = *(str1+i+count);
}
}
}
}
}

复制代码