本文向给大家分享求子回文串的长度相关知识,同时小编也会对回文子串进行解释,如果能解决您在求子回文串的长度方面面临的问题,请收藏关注本站,现在开始吧!
java找出字符串中的数字并输出
Java code
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.ArrayList;
import java.util.List;
public class Palindrome {
/* 找出一个字符串中最长的回文子串
* 从字符串中第i个字符开始的所有非空回文子串的个数, 记作为Ci. 此方法的复杂度为
* O(C1 + C2 + ... + Cn)
* 当字符串中任意两个非空回文子串的起始位置不同时, C1 = C2 = ... = Cn = 1, 复杂度为O(N);
* 当字符串所有字符均为同一字符时, Ci = n - i, 此时复杂度为O(N*N);
* 在多数情况下, 此方法的复杂度远低于O(N*N).
*/
public List<String> getLongestPalindrome(String theString) {
int strLen = theString.length();
List<String> results = new ArrayList<String>(strLen);
if (strLen == 0) {
return results;
}
// 从第i个位置开始的所有回文子串的结束位置.
int[] endIndice = new int[strLen + 1];
// endIndice中有效数据的长度.
int numberOfPalindromes = 1;
// 最长回文子串的长度. 对于非空串至少可以找到长度为1的回文子串.
int maxLen = 1;
results.add(theString.substring(strLen - 1));
// 计算从第i个位置开始的所有回文子串. 这样的子串分为三种:
// 1. 在从第i+1个位置开始的回文子串的基础上, 在两端加上相同的字符;
// 2. 长度为1的回文子串;
// 3. 空串.
for (int i = strLen - 2; i >= 0; i--) {
int j = 0, k = 0;
while (j < numberOfPalindromes) {
if (theString.charAt(i) == theString.charAt(endIndice[j])) {
endIndice[k] = endIndice[j] + 1;
int newLength = endIndice[k] - i;
if (newLength >= maxLen) {
if (newLength > maxLen) {
maxLen = newLength;
results.clear();
}
results.add(theString.substring(i, endIndice[k]));
}
if (endIndice[k] < strLen) {
k++;
}
}
j++;
}
// 加入长度为1的子串
endIndice[k++] = i + 1;
if (maxLen == 1) {
results.add(theString.substring(i, i + 1));
}
// 加入空串
endIndice[k++] = i;
numberOfPalindromes = k;
}
return results;
}
public static void main(String[] args) {
Palindrome p = new Palindrome();
printList(p.getLongestPalindrome("gabcecbaefd"));
printList(p.getLongestPalindrome("bbcbaefccfg"));
printList(p.getLongestPalindrome("aaaaaaaaaaa"));
printList(p.getLongestPalindrome("abcdefghijk"));
printList(p.getLongestPalindrome("abcdeeddejk"));
printList(p.getLongestPalindrome(""));
}
public static void printList(List<? extends Object> list) {
System.out.println("**************************");
System.out.println(list.size() + " result(s):");
for (Object o : list) {
System.out.println(o);
}
}
}
java找出字符串中第一个只出现一次的字符
public class test {
public static void main(String args[]) {
String s = "abaccdccabcdcba";
System.out.println(getMax(s));
}
static String getMax(String s){
char[] b = s.toCharArray();
int start = 0;
int maxLength = 0;
for(int i = 0;i<b.length;i++){
int tempLength = 0;
int tempStart = 0;
for(int j=0;j<=i&&j<b.length-i;j++){
System.out.println(b[i-j]+"==="+b[i+j]);
if(b[i-j]==b[i+j]){
tempStart = i-j;
tempLength +=2;
}else
break;
}
if(tempLength>maxLength){
start = tempStart;
maxLength= tempLength;
}
System.out.println("临时起始位置"+tempStart+":"+tempLength+"|起始位置"+start+":"+maxLength);
}
String result = s.substring(start, maxLength);
return result;
}
}额 写了个 虽然效率不高 但能实现了
以上就是与求子回文串的长度以及回文子串的相关内容,也是关于java找出字符串中的数字并输出的分享。看完求子回文串的长度一文后,希望这对大家有所帮助!
声明:求子回文串的长度 求子串是什么意思文字图片内容来源于会员投稿,版权归其所有,转载请注明出处。卜安居系信息发布平台,仅提供信息存储空间服务,接受投稿是出于传递更多信息、供广大网友交流学习之目的。