找出多个字符串中的最大公共子字符串，求代码重构 - 黑马程序员技术交流社区

//找出多个字符串中的最大公共子字符串，如“nbitheimanb”和“itheia”的最大子串是：”ithei”。（C语言）
#include <stdio.h>
#include <string.h>
int main()
{
char *s1 = "nbitheimanbcf";
char *s2 = "itheia";
void maxPublicString(char *s1,char *s2);
maxPublicString(s2,s1);
return 0;
}
void maxPublicString(char *s1,char *s2)
{
//分别求出s1,s2字符串的长度
int s1len = strlen(s1);
int s2len = strlen(s2);
//记录相同元素下标，记录相同的元素个数
int index = 0 ,count = 0;
//遍历s1
for(int i = 0; i<s1len ; i++)
{
//遍历s2
for(int j = 0; j<s2len; j++)
{
//取出s2的每一个元素s1进行比较，
if(s1[i]==s2[j])
{
//如果有相同的元素，则同时都往后面移动
for(int k = 1 ;s1[i+k]==s2[j+k] && s2[j+k]!='\0' && s1[i+k]!='\0' ;k++)
{
//选出最大公共字符串
if(k>count)
{
//记录最大公共字符串长度的下标
count =k;
//记录最大公共字符串长度的个数
index = i;
}
}
}
}
}
if(count == 0)
{
printf("没有找到最大公共子串\n");
}
else
{
printf("最长公共字串是:");
for(int i = 0 ; i<=count; i++)
{
printf("%c",s1[index+i]);
}
}
printf("\n");
}

复制代码

[Java] 纯文本查看 复制代码

/*

 * 注：此程序在公共子字符串长度为1的情况下，会出现下例中的现象。

 * 

 * 例："abbbbbbc"和"addddc" 的结果为a(严格来说a和c都应该算作公共子字符串).

 */

import java.util.Scanner;



public class Test {

        public static void main(String[] args) {

                Scanner sc = new Scanner(System.in);

                System.out.println("请输入字符串的个数：");

                int num = Integer.parseInt(sc.nextLine());



                // 该数组用于存储键盘录入的字符串

                String[] arr = new String[num];

                // 该数组用于备份字符串

                String[] arr2 = new String[num];



                // 存储字符串

                for (int x = 0; x < num; x++) {

                        System.out.println("请输入第" + (x + 1) + "个字符串：");

                        String s = sc.nextLine();

                        arr[x] = s;

                        arr2[x] = s;

                }



                // 获取所有字符串的公共子字符串

                String commonString = getAllCommonString(arr);

                System.out.println("您输入的字符串为：");



                // 遍历数组

                for (String s : arr2) {

                        System.out.println(s);

                }



                // 考虑到可能没有公共子字符串

                if (commonString.isEmpty()) {

                        System.out.println("没有公共的子字符串.");

                } else {

                        System.out.println("这些字符串的最大公共子字符串为：" + commonString);

                }

        }



        // 这是获取多个字符串中的最大公共子字符串的方法

        public static String getAllCommonString(String[] arr) {

                for (int x = 0; x < arr.length - 1; x++) {

                        arr[x + 1] = getCommonString(arr[x], arr[x + 1]);

                }



                return arr[arr.length - 1];

        }



        // 这是获取两个字符串的最大公共子字符串的方法

        public static String getCommonString(String str1, String str2) {

                String max = str1.length() > str2.length() ? str1 : str2;

                String min = max == str1 ? str2 : str1;



                for (int x = 0; x < min.length(); x++) {

                        for (int start = 0, end = min.length() - x; end <= min.length(); start++, end++) {

                                String sub = min.substring(start, end);

                                if (max.contains(sub)) {

                                        return sub;

                                }

                        }

                }



                // 这里不返回null的原因是为了避免空指针异常

                // 如果确实没有公共子字符串则返回的内容为空

                String s = "";

                return s;

        }

}