求字符串的最大回文子串

转载请注明出处：http://blog.csdn.net/xiaojimanman/article/details/48974425

http://www.llwjy.com/blogdetail/46b46cdd7d80de938ac159922c0060ca.html

个人博客站已经上线了，网址 www.llwjy.com ~欢迎各位吐槽~

-------------------------------------------------------------------------------------------------

问题描述

      在之前的一篇博客《java实现字符串匹配问题之求两个字符串的最大公共子串》中介绍了如何求两个字符串的公共子串，今天在网上看到一个问题，是求一个字符串的最大回文子串的，比如：

"a"的回文子串是"a"

"abac"的回文子串是"aba"

      对于这个问题的实现，自己想通过已有公共子串来实现，具体思路如下：求字符串s1的最大回文子串，首先构造一个s1的反转字符串s2，然后求s1、s2的最大公共子串，求出的最大公共子串就是s1的最大回文子串（自己手动测试了很多事例，都是正确的，但是没有找到相关的理论支持）。

代码实现

      在原有代码的基础上添加一个方法，具体如下：

public List<String> getPalindromeStr(String s) {
	if (s == null || "".equals(s)) {
		return null;
	}
	StringBuffer sb = new StringBuffer(s);
	String s2 = sb.reverse().toString();
	return getMaxChildString(s, s2);
}
           

      该工具类完整代码如下：

/**  
 *@Description:  字符串的公共子串
 */ 
package com.lulei.util;  

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class StringFactor {
	private String str1;
	private String str2;
	private int maxLength = -1;
	
	/**
	 * @param s1
	 * @param s2
	 * @return
	 * @Author:lulei  
	 * @Description: 获取所有公共子串，并排序
	 */
	public List<String> getAllChildString(String s1, String s2) {
		List<String> strs = new ArrayList<String>();
		if (s1 == null || s2 == null)  {
			return strs;
		}
		this.str1 = s1;
		this.str2 = s2;
		//求所有公因子字符串，保存信息为相对第二个字符串的起始位置和长度
		List<ChildString> childStrings = new ArrayList<ChildString>();
		for (int i = 0; i < this.str1.length(); i++) {
			getAllChildString(i, 0, childStrings);
		}
		for (int i = 1; i < this.str2.length(); i++) {
			getAllChildString(0, i, childStrings);
		}
		//排序
		sort(childStrings);
		for (ChildString s: childStrings) {
			strs.add(this.str2.substring(s.maxStart, s.maxStart + s.maxLength));
		}
		return strs;
	}
	
	/**
	 * @param s1
	 * @param s2
	 * @return
	 * @Author:lulei  
	 * @Description: 获取最大公共子串
	 */
	public List<String> getMaxChildString(String s1, String s2) {
		List<String> strs = new ArrayList<String>();
		if (s1 == null || s2 == null)  {
			return strs;
		}
		this.str1 = s1;
		this.str2 = s2;
		//求所有公因子字符串，保存信息为相对第二个字符串的起始位置和长度
		List<ChildString> childStrings = new ArrayList<ChildString>();
		for (int i = 0; i < this.str1.length(); i++) {
			getMaxChildString(i, 0, childStrings);
		}
		for (int i = 1; i < this.str2.length(); i++) {
			getMaxChildString(0, i, childStrings);
		}
		for (ChildString s: childStrings) {
			strs.add(this.str2.substring(s.maxStart, s.maxStart + s.maxLength));
		}
		return strs;
	}
	
	/**
	 * @param i
	 * @param j
	 * @param sortBean
	 * @Author:lulei  
	 * @Description: 查找所有子串
	 */
	private void getAllChildString(int i, int j, List<ChildString> sortBean) {
		int length = 0;
		int start = j;
		for (; i < this.str1.length() && j < this.str2.length(); i++,j++) {
			if (this.str1.charAt(i) == this.str2.charAt(j)) {
				length++;
			} else {
				//直接add，保存所有子串
				if (length > 0) {
					sortBean.add(new ChildString(length, start));
					length = 0;
				}
				start = j + 1;
			}
			if (i == this.str1.length() - 1 || j == this.str2.length() - 1) {
				//直接add，保存所有子串
				if (length > 0) {
					sortBean.add(new ChildString(length, start));
				}
				//对角线结尾，length置0
				length = 0;
			}
		}
	}
	
	/**
	 * @param i
	 * @param j
	 * @param sortBean
	 * @Author:lulei  
	 * @Description: 保存当前最大子串
	 */
	private void getMaxChildString(int i, int j, List<ChildString> sortBean) {
		int length = 0;
		int start = j;
		for (; i < this.str1.length() && j < this.str2.length(); i++,j++) {
			if (this.str1.charAt(i) == this.str2.charAt(j)) {
				length++;
			} else {
				//下面的判断，只保存当前最大的子串
				if (length == maxLength) {
					sortBean.add(new ChildString(length, start));
				} else if (length > maxLength) {
					sortBean.clear();
					maxLength = length;
					sortBean.add(new ChildString(length, start));
				}
				length = 0;
				start = j + 1;
			}
			if (i == this.str1.length() - 1 || j == this.str2.length() - 1) {
				//下面的判断，只保存当前最大的子串
				if (length == maxLength) {
					sortBean.add(new ChildString(length, start));
				} else if (length > maxLength) {
					sortBean.clear();
					maxLength = length;
					sortBean.add(new ChildString(length, start));
				}
				//对角线结尾，length置0
				length = 0;
			}
		}
	}
	
	/**
	 *@Description:  公共子串类
	 *@Author:lulei  
	 *@Version:1.1.0
	 */
	private class ChildString {
		int maxLength;
		int maxStart;
		
		ChildString(int maxLength, int maxStart){
			this.maxLength = maxLength;
			this.maxStart = maxStart;
		}
	}
	
	/**
	 * @param list
	 * @Author:lulei  
	 * @Description: 降序排列
	 */
	private void sort(List<ChildString> list) {
		Collections.sort(list, new Comparator<ChildString>(){
			public int compare(ChildString o1, ChildString o2) {
				return o2.maxLength - o1.maxLength;
			}
		});
	}
	
	/**
	 * @param s
	 * @return
	 * @Author:lulei  
	 * @Description:返回字符串的最大回文子串
	 */
	public List<String> getPalindromeStr(String s) {
		if (s == null || "".equals(s)) {
			return null;
		}
		StringBuffer sb = new StringBuffer(s);
		String s2 = sb.reverse().toString();
		return getMaxChildString(s, s2);
	}

	public static void main(String[] args) {
		String s1 = "refer";
		String s2 = "ref";
		System.out.println("--------------------------all--------------------------");
		for (String s : new StringFactor().getAllChildString(s1, s2)) {
			System.out.println(s);
		}
		System.out.println("--------------------------max--------------------------");
		for (String s : new StringFactor().getMaxChildString(s1, s2)) {
			System.out.println(s);
		}
		System.out.println("--------------------------huiwen--------------------------");
		for (String s : new StringFactor().getPalindromeStr(s1)) {
			System.out.println(s);
		}
	}

}
           

运行结果

-------------------------------------------------------------------------------------------------

小福利

-------------------------------------------------------------------------------------------------

      个人在极客学院上《Lucene案例开发》课程已经上线了（目前上线到第二课），欢迎大家吐槽~

第一课：Lucene概述

第二课：Lucene 常用功能介绍

第三课：网络爬虫

第四课：数据库连接池

第五课：小说网站的采集