本文共 1680 字，大约阅读时间需要 5 分钟。

版权声明

• 本文原创作者：谷哥的小弟
• 作者博客地址：http://blog.csdn.net/lfdfhl

题目分析

在编程之前，我们先来分析题目。

要求

找出两个字符串中的最大子串，即最大的交集。例如：udappyzk和xzhappymol最大子串为appy

步骤

• 1、找出两个字符串中的较短者
• 2、分别将较短子串除去0,1,2,3,4……个元素
• 3、判断除去X个元素后的较短子串是否在较长字符串中出现

示例

以题目中较短字符串udappyzk为例

• 1、去除0个元素的情况，有1种操作，得到本身字符串作为最大子串
• 2、去除1个元素的情况，有2种操作，即分别去除第一个和最后一个得到dappyzk和udappyz
• 3、去除2个元素的情况，有3种操作，即去掉头两个和去掉尾两个和头尾各去一个即得到appyzk和udappy和dappyz
• 4、去除3个元素的情况，有4种操作，即去掉头三个和去掉尾三个和头去一个尾去两个和头去两个尾一个，即ppyzk和udapp和dappy和appyz

小结

综上分析：

• 1、去除较短元素的N个元素，共有N+1种可能
• 2、头部去元素个数 + 尾部去元素个数 = N

代码实现

代码实现如下：

package com.algorithm;/** * 本文作者：谷哥的小弟  * 博客地址：http://blog.csdn.net/lfdfhl */public class StringAlgorithm {
   	public static void main(String[] args) {
   		String firstString = "udappyzk";		String secondString = "xzhappymol";		String commonMaxSubstring = findCommonMaxSubstring(firstString, secondString);		System.out.println("commonMaxSubstring=" + commonMaxSubstring);	}	// 求两个字符串的最大交集	public static String findCommonMaxSubstring(String firstString, String secondString) {
   		String longerString = null;		String shorterString = null;		String result = null;		if (firstString.length() >= secondString.length()) {
   			longerString = firstString;			shorterString = secondString;		} else {
   			longerString = secondString;			shorterString = firstString;		}		int shorterStringLength = shorterString.length();		for (int i = 0; i < shorterStringLength; i++) {
   			for (int j = 0; j <= i; j++) {
   				int start = j;				int end = shorterStringLength - i + j;				result = shorterString.substring(start, end);				int index = longerString.indexOf(result);				if (index != -1) {
   					return result;				}else {
   					result = null;				}			}		}		return result;	}}

运行结果

转载地址：https://it9527.blog.csdn.net/article/details/109340309 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！