查找给定字符串的所有回文子串（Java）

2024 年 9 月 10 日 | 阅读 8 分钟

给定一个字符串 str，我们的任务是找到那些是回文形式的子字符串，并且它们应该是给定字符串中所有不同的回文子字符串。

示例 1

输入

输出

不同的回文子字符串总共有 8 个。它们是

a
b
bb
bbb
bbcbb
bcb
c
e

示例 2

输入

输出

不同的回文子字符串总共有 5 个。它们是

a
b
c
d
e

示例 3

输入

输出

不同的回文子字符串总共有 11 个。它们是

i
ippi
issi
ississi
m
p
pp
s
sis
ss
ssiss

方法：使用暴力算法

算法

步骤 1：声明一个二维布尔数组，并必须以对角线的方式填充它。

步骤 2：验证每个 K。即 (0,1,2,.....)

步骤 3：假设 K=0，表示只有一个元素。因为单个字符是回文，在这种情况下我们得到 true。

步骤 4：如果 K = 1，我们确定两端是否相同并返回 true；否则，我们返回 false。

步骤 5：如果 K 不相同，我们检查两端是否相同，并查看 ar[i+1][j-1] 是否返回 true；如果是，我们将其设置为 true；如果不是，则将其设置为 false。每次找到 true 时，我们将字符串添加到 set 数据结构中。

步骤 6：返回回文子字符串。

实施

文件名：PlaindromeSubstringBrute.java

import java.io.*;
import java.util.*;
public class PlaindromeSubstringBrute
{
	static int palinSubstring(String s, Set<String> set)
	{
	    int N = s.length();
	    // create a 2-D array which stores the
	    //Whether a string is a palindrome or not
	    boolean ar[][] = new boolean[N][N];
	    for (int K = 0; K < N; K++) 
	    {
		// iterating the string by taking
		//The substring length as K
		for (int i = 0, j = K; j < N; i++, j++) 
		{
		       // checking a substring is of length only  
		      // single character
		      if (K == 0)
		      {
		           ar[i][j] = true;   
		       }
		       // checking a substring is of length 2
		       else if (K == 1)
		        {
			  ar[i][j] = s.charAt(i) == s.charAt(j);   
		        }
		       //If substring length greater than 2
		      else
		      {
		             ar[i][j] = (s.charAt(i) == s.charAt(j) && ar[i + 1][j - 1]);   
		       }
		       // If the substring is a palindrome
		       // add it to the set
		       if (ar[i][j])
		       {
		             set.add(s.substring(i, j + 1));  
		       }
		}
	       }
	        return set.size();
	}
	public static void main(String[] args)
	{
		String s = "abbcbbbe";
		Set<String> set = new TreeSet<>();
		palinSubstring(s, set);
		System.out.println("The total distinct palindromic substrings are: " + palinSubstring(s, set));
		for (String str : set)
			System.out.println(str);
		System.out.println("The total number of distinct palindromic substrings are : " + set.size());
	}
}

输出

The total distinct palindromic substrings are: 8
a
b
bb
bbb
bbcbb
bcb
c
e
The total number of distinct palindromic substrings are : 8

复杂度分析

时间复杂度为 O(N² * log(N))，其中 'N' 表示所取字符串的长度，因为我们在遍历数组时将元素插入集合需要 log(N) 时间。空间复杂度为 O(N²)，因为使用了二维数组。

方法：使用 KMP（Knuth-Morris-Pratt）算法

在此方法中，我们采用了 KMP 技术来有效地查找回文子字符串。它通过迭代遍历字符串并比较字符来查找匹配的前缀和后缀。当识别出匹配的后缀和前缀时，KMP 数组会被更新以跟踪匹配前缀的长度。如果找到回文，则将回文数组中的匹配元素设置为 false，以防止其被计算多次。通过消除对回文子字符串不必要的计数，这种优化可以精确地计算出唯一的。

算法

步骤 1：声明 N 来初始化给定字符串 "str" 的长度，然后初始化 arr[N][N] 来验证子字符串是否为回文。

步骤 2：对于单个字符，将 arr[i][i] 初始化为 true。

步骤 3：查找长度为二的回文，识别相邻的字符。

步骤 4：迭代长度大于二的子字符串以查找回文，

步骤 5：如果字符串的两端匹配并且内部子字符串是回文，则更新 arr[i][j]。

步骤 6：为了增强回文检测，使用 KMP 方法。

步骤 7：确定前缀和后缀，以确保回文计数准确。

步骤 8：在遍历子字符串时，将字符添加到每个子字符串以创建新的子字符串。

步骤 9：如果找到一个子字符串是回文，则打印该子字符串并增加计数。

步骤 10：打印不同回文子字符串的总数。

实施

文件名：plaindromeSubstringsDP.java

import java. util.*;
import java.io.*;
public class plaindromeSubstringsDP
{
    public static int palinsubstring(String str)
    {
    	int N = str.length();
    	//  We may solve this in O(N^2) by utilizing 
    	// dynamic programming to save the value of 
    	// the "arr" array, which indicates whether 
    	// a substring is a palindrome or not
    	// (1) if (i, j) is a palindrome, else false (0)
    	boolean[][] arr = new boolean[N][N];
    	for (int i = 0; i < N; i++) 
    	{
        	// base case to check every char is palindrome
        	arr[i][i] = true;
        	// check for every substring of length 2
        	if (i < N - 1 && str.charAt(i) == str.charAt(i + 1)) 
        	{
        		arr[i][i + 1] = true;
        	}
    	}
    	//Seek out palindromes in each substring 
    	// with a length greater than 2.
    	for (int l = 3; l <= N; l++) 
    	{
        	for (int i = 0; i + l - 1 < N; i++) 
        	{
        		if (str.charAt(i) == str.charAt(i + (l - 1)) && arr[i + 1][i + (l - 1) - 1]) 
        		{
        	    	arr[i][i + (l - 1)] = true;
        		}
        	}
    	}
        // apply kmp algorithm 
    	int[] kmp = new int[N];
    	for (int i = 0; i < N; i++) 
    	{
        	// starting kmp for each and every i from 0 to N-1
        	int j = 0, k = 1;
        	while (k + i < N) 
        	{
        		if (str.charAt(j + i) == str.charAt(k + i))
        		{
            		// turn the suffix into a false value 
            		// In the case that this suffix is a palindrome, 
            		// it is already included in the prefix.
        		    arr[k + i - j][k + i] = false;
        		    kmp[k++] = ++j;
        		}
        		else if (j > 0) 
        		{
        		    j = kmp[j - 1];
        		}
        		else 
        		{
        		    kmp[k++] = 0;
        		}
        	}
    	}
    	int cnt = 0;
    	System.out.println("The total distinct palindromic substrings are:");
    	for (int i = 0; i < N; i++) 
    	{
        	String s = "";
        	for (int j = i; j < N; j++) 
        	{
        		s += str.charAt(j);
        		if (arr[i][j])
        		{
            		// count the number of resulting unique 
            		// substrings and display that substring
            		cnt++;
            		System.out.println(s);
        		}
        	}
    	}
    	System.out.println("The total number of distinct palindromic substrings are : " + cnt);
    	return 0;
    }
    public static void main(String[] args)
    {
    	String str = "abbcbbbe";
    	palinsubstring(str);
    }
}

输出

The total distinct palindromic substrings are:
a
b
bb
bbcbb
bcb
c
bbb
e
The total number of distinct palindromic substrings are : 8

复杂度分析

时间复杂度为 O(N²)，空间复杂度为 O(N²)，其中 'N' 表示给定字符串的长度。

方法：Manacher 算法

通过考虑每个字母作为枢轴，从两侧扩展，以确定查询中以枢轴字符为中心的偶数和奇数长度回文的长度。将结果存储在两个数组（odd & even）中。将前一个阶段识别出的每个回文都放入哈希映射中。为了创建唯一的单字母回文子字符串，还将字符串中的每个单独字符插入到 HashMap 中。

最后一步是打印存储在哈希映射中的每个值（由于哈希映射的属性，只会哈希不同的项）。通过查看映射的大小，可以确定不同连续回文子字符串的数量。

算法

步骤 1：声明一个名为 m 的 TreeMap，以存储不同的回文子字符串及其计数。

步骤 2：找出输入字符串 str 的长度，并初始化一个二维数组 row 来存储回文长度。

步骤 3：为了简化回文识别，在字符串的开头和结尾分别附加特殊字符 '@' 和 '#'。

步骤 4：使用两个循环遍历字符串：一个用于偶数长度的回文，另一个用于奇数长度的回文。

步骤 5：对于字符串中的每个字符，执行以下步骤。

步骤 5.1：检查以使当前字符周围的回文更大。

步骤 5.2：更新 row 数组中的回文长度。

步骤 5.3：将找到的回文子字符串添加到 m TreeMap 中。

步骤 6：打印 m 中保留的所有不同的回文子字符串。

步骤 7：确定 TreeMap m 的大小，以打印不同回文子字符串的总数。

实施

文件名：PalindromeSubstringMancherAlgo.java

import java.io.*;
import java.util.Map;
import java.util.TreeMap;
public class PalindromeSubstringMancherAlgo
{	 
	// The function prints every unique 
	// palindrome in the substrings of str.
	static void palindromeSubStrs(String str)
	{
		// map<string, int> m;
		TreeMap<String , Integer> m = new TreeMap<>();
		int N = str.length();
		// table for results storage, with two rows 
		// for even- and odd-length palindromes
		int[][] row = new int[2][N+1];
		// Locate every substring palindrome in the 
		// given input string and insert "guards" 
		// to make iterating over str easier.
		str = "@" + str + "#";
		for (int j = 0; j <= 1; j++)
		{
			int rpalin = 0; // length of 'palindrome radius'
			row[j][0] = 0;
			int i = 1;
			while (i <= N)
			{
				// An attempt to expand the palindrome centered at i
				while (str.charAt(i - rpalin - 1) == str.charAt(i + j + rpalin))
					rpalin++; 
				// Increasing the length of + palindromic radius 
				// as and when a valid palindrome is found
                // Assigning the palindromic length that 
                // was identified to the odd/even length array
				row[j][i] = rpalin;
				int k = 1;
				while ((row[j][i - k] != rpalin - k) && (k < rpalin))
				{
					row[j][i + k] = Math.min(row[j][i - k], rpalin - k);
					k++;
				}
				rpalin = Math.max(rpalin - k,0);
				i += k;
			}
		}
		// remove 'guards'
		str = str.substring(1, str.length()-1);
		// Put every palindrome that was obtained 
		// into a hash map in order to identify 
		// only distinct palindromes.
		m.put(str.substring(0,1), 1);
		for (int i = 1; i < N; i++)
		{
			for (int j = 0; j <= 1; j++)
				for (int rpalin = row[j][i]; rpalin > 0; rpalin--)
				m.put(str.substring(i - rpalin - 1, i - rpalin - 1 + 2 * rpalin + j), 1);
			m.put(str.substring(i, i + 1), 1);
		}
		// printing every unique palindrome from the hash map
	System.out.println("The total distinct palindromic substrings are:");
	for (Map.Entry<String, Integer> ii:m.entrySet())
		System.out.println(ii.getKey());
	System.out.println("The total number of distinct palindromic substrings are : " + (m.size()));
	}
	public static void main(String args[])
	{
	    String str = "abbcbbbe";
		palindromeSubStrs(str);
	}
}

输出

The total distinct palindromic substrings are:
a
b
bb
bbb
bbcbb
bcb
c
e
The total number of distinct palindromic substrings are : 8

复杂度分析

上述代码的时间复杂度为 O(N²)，其中 'N' 表示给定字符串的长度，空间复杂度为 O(N)。

下一话题Java 中查找字符串是否为 K 回文

查找给定字符串的所有回文子串（Java）

示例 1

示例 2

示例 3

方法：使用暴力算法

算法

实施

方法：使用 KMP（Knuth-Morris-Pratt）算法

算法

实施

方法：Manacher 算法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

查找给定字符串的所有回文子串（Java）

示例 1

示例 2

示例 3

方法：使用暴力算法

算法

实施

方法：使用 KMP（Knuth-Morris-Pratt）算法

算法

实施

方法：Manacher 算法

算法

实施

相关帖子

Ways to Create an Object in Java

如何生成 JVM 堆内存转储

How to Update Java

设计自定义 Java 连接池

如何在 Java 中将非守护线程设为守护线程

使用 Java 泛型将 Set 转换为 Stream 的程序

BreakIterator previous() method in Java with Examples

Java 程序删除目录

Java 静态类型与动态类型

Java 中的最大正方形矩阵问题

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器