有一個字串 s。為使字串回文而重新排列的子串的最小長度是多少。
例子：
輸入： abbaabbca
輸出： 4
我可以重新排列從索引4 到 7 (abbc) 的子字串，并得到abbacabba
保證重排后有回文。
有沒有辦法通過修改 Manacher 或其他一些文本演算法來解決它？
謝謝。
uj5u.com熱心網友回復：
你可以這樣使用
bool morethanone(string s, char c)
{
// Count variable
bool res = false;
for (int i=0;i < s.length(); i )
// checking character in string
if (s[i] == c)
res ;
if(res > 1)
return true;
else
return false;
}
int getsubstringlength(string text)
{
int result = 0;
for (int i = 0; i < text.length(); i )
{
if(morethanone(text, text[i]))
result ;
}
return result;
}
uj5u.com熱心網友回復：
我認為標準文本處理演算法并非如此。這很簡單，您不需要它們 - 字串只有一個重新洗牌的部分，因此可能會出現四種情況。
'ppssXXXXXXXpp''ppXXXXXsssspp''ppsssiiiXXXpp''ppXXXiiissspp'
在哪里
- pp是已經回文的外部部分（可能為零）
- XX是我們重新洗牌的部分
- ss是我們保留原樣的部分（并重新調整 XX 以匹配它）
- ii是中心周圍的內部部分，它也已經是回文（可能為零）
我們可以先檢查和裁剪外回文部分，留下'ssXXXXXXX', 'XXXXXssss','sssiiiXXX'或'XXXiiisss'
然后我們使用對稱性——如果中間部分存在，我們可以任意選擇我們保留哪一邊，我們洗牌以適應另一邊，所以我們只做一個。當沒有中間回文部分時，我們只需從相反的方向開始運行相同的檢查，然后我們選擇給出較短子串的那個
所以，讓我們從頭開始。我們將簡單地一個接一個字符
's--------'
'ss-------'
'sss------'
并在字串的其余部分不再與其余部分匹配時停止。
什么時候會發生？當字串的 'sss... 部分已經吞噬了所有出現的字符的一半以上時，那么它就會在另一側丟失并且無法通過改組來匹配。
另一方面，在通過字串的中間之后，我們總是會吃掉每個字符出現次數的一半以上。所以可能出現三種情況。
- 我們缺少中間部分。在這種情況下，我們找到了要重新洗牌的字串。
'sssXXXXXXXXXXXX' - 我們到達中間。然后我們也可以搜索回文的內部部分，產生類似
'ssssiiiiXXXX' - 有一種特殊情況，您到達奇數邊字串的中間 - 那里必須有一個奇數計數字符。如果它不存在，您將必須繼續執行 1)
結果演算法（在java中，已經在這里嘗試過）：
package palindrometest;
import java.io.*;
import java.util.*;
import java.util.stream.*;
class PalindromeTest {
static int[] findReshuffleRange( String s ) {
// first the easy part,
//split away the already palindromatic start and end if there is any
int lo = 0, hi = s.length()-1;
while(true) {
if( lo >= hi ) {
return new int[]{0,0}; // entire string a palindrome
}
if( s.charAt(lo) != s.charAt(hi) ) {
break;
}
lo ;
hi--;
}
// now we compute the char counts and things based on them
Map<Character,Integer> charCounts = countChars( s, lo, hi );
if( !palindromePossible( charCounts ) ) {
return null;
}
Map<Character,Integer> halfCounts = halfValues( charCounts );
char middleChar = 0;
if( (s.length() % 2) != 0 ) { // only an odd-sized string has a middle char
middleChar = findMiddleChar( charCounts );
}
// try from the beginning first
int fromStart[] = new int[2];
if( findMiddlePart( fromStart, s, lo, hi, halfCounts, middleChar, false ) ) {
// if the middle palindromatic part exist, the situation is symmetric
// we don't have to check the opposite direction
return fromStart;
}
// try from the end
int fromEnd[] = new int[2];
findMiddlePart( fromEnd, s, lo, hi, halfCounts, middleChar, true );
// take the shorter
if( fromEnd[1]-fromEnd[0] < fromStart[1]-fromStart[0] ) {
return fromEnd;
} else {
return fromStart;
}
}
static boolean findMiddlePart( int[] result, String s, int lo, int hi, Map<Character,Integer> halfCounts, char middleChar, boolean backwards ) {
Map<Character,Integer> limits = new HashMap<>(halfCounts);
int pos, direction, end, oth;
if( backwards ) {
pos = hi;
direction = -1;
end = (lo hi)/2; // mid rounded down
oth = (lo hi 1)/2; // mid rounded up
} else {
pos = lo;
direction = 1;
end = (lo hi 1)/2; // mid rounded up
oth = (lo hi)/2; // mid rounded down
}
// scan until we run out of the limits
while(true) {
char c = s.charAt(pos);
int limit = limits.get(c);
if( limit <= 0 ) {
break;
}
limits.put(c,limit-1);
pos = direction;
}
// whether we reached the middle
boolean middleExists = pos == end && ( oth != end || s.charAt(end) == middleChar );
if( middleExists ) {
// scan through the middle until we find the first non-palindromic character
while( s.charAt(pos) == s.charAt(oth) ) {
pos = direction;
oth -= direction;
}
}
// prepare the resulting interval
if( backwards ) {
result[0] = lo;
result[1] = pos 1;
} else {
result[0] = pos;
result[1] = hi 1;
}
return middleExists;
}
static Map<Character,Integer> countChars( String s, int lo, int hi ) {
Map<Character,Integer> charCounts = new HashMap<>();
for( int i = lo ; i <= hi ; i ) {
char c = s.charAt(i);
int cnt = charCounts.getOrDefault(c,0);
charCounts.put(c,cnt 1);
}
return charCounts;
}
static boolean palindromePossible(Map<Character,Integer> charCounts) {
int oddCnt = 0;
for( int cnt : charCounts.values() ) {
if( (cnt % 2) != 0 ) {
oddCnt ;
if( oddCnt > 1 ) {
return false; // can not be made palindromic
}
}
}
return true;
}
static char findMiddleChar( Map<Character,Integer> charCounts ) {
Map<Character,Integer> halfCounts = new HashMap<>();
for( Map.Entry<Character,Integer> e : charCounts.entrySet() ) {
char c = e.getKey();
int cnt = e.getValue();
if( (cnt % 2) != 0 ) {
return c;
}
}
return 0;
}
static Map<Character,Integer> halfValues( Map<Character,Integer> charCounts ) {
Map<Character,Integer> halfCounts = new HashMap<>();
for( Map.Entry<Character,Integer> e : charCounts.entrySet() ) {
char c = e.getKey();
int cnt = e.getValue();
halfCounts.put(c,cnt/2); // we round *down*
}
return halfCounts;
}
static String repeat(char c, int cnt ) {
return cnt <= 0 ? "" : String.format("%" cnt "s","").replace(" ","" c);
}
static void testReshuffle(String s ) {
int rng[] = findReshuffleRange( s );
if( rng == null ) {
System.out.println("Result : '" s "' is not palindromizable");
} else if( rng[0] == rng[1] ) {
System.out.println("Result : whole '" s "' is a palindrome");
} else {
System.out.println("Result : '" s "'");
System.out.println(" " repeat('-',rng[0]) repeat('X',rng[1]-rng[0]) repeat('-',s.length()-rng[1]) );
}
}
public static void main (String[] args) {
testReshuffle( "abcdefedcba" );
testReshuffle( "abcdcdeeba" );
testReshuffle( "abcfdeedcba" );
testReshuffle( "abcdeedbca" );
testReshuffle( "abcdefcdeba" );
testReshuffle( "abcdefgfcdeba" );
testReshuffle( "accdefcdeba" );
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/386266.html
上一篇：將指標傳遞給類的建構式