使用Java编写一个对一个固定字符串找出最长平台并输出,可以输出多个
时间: 2024-11-13 16:28:40 浏览: 10
Alg4:算法 4 课程作业
在Java中,我们可以编写一个函数来寻找给定字符串中最长的回文子串。回文是一种正读反读都一样的字符序列,比如"madam"或"racecar"。下面是一个简单的示例,使用动态规划方法,即Manacher's Algorithm,来找到最长回文:
```java
public class Main {
public static void main(String[] args) {
String str = "babad"; // 测试输入
System.out.println("最长回文子串为: " + longestPalindrome(str));
}
public static String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int n = s.length();
char[] p = new char[n];
p[0] = p[n - 1] = '#';
for (int i = 0; i < n; i++) {
p[i + 1] = s.charAt(i);
}
int center = 0, right = 0;
for (int i = 1; i < n; i++) {
int len1 = Math.min(right - i, p[i]);
int len2 = Math.min(right + 1 - i, p[n - i]);
int len = Math.max(len1, len2);
if (i + len > right) {
center = i;
right = i + len;
}
p[i] = len;
}
int maxLen = 0, start = 0;
for (int i = 1; i <= right; i++) {
if (p[i] > maxLen) {
maxLen = p[i];
start = (i - maxLen) / 2;
}
}
return s.substring(start, start + maxLen);
}
}
```
这个程序首先将原字符串加上特殊字符`#`作为边界,然后遍历字符串查找回文子串。最后返回找到的最长回文子串。
阅读全文