반응형
주어진 쿠폰에서 가장 긴 회문을 반환하는 함수 작성
예 : "abaccddccefe"문자열의 "ccddcc"
해결을 생각했지만 O (n ^ 2) 시간에 실행됩니다.
알고 1 :
단계 : 무차별 대입 방법
i = 1 ~ i에 대해 2 개의 루프 가 array.length보다 작습니다.
j = i + 1 ~ j가 array.length보다 작 으면 -1 입니다.- 이렇게하면 배열에서 가능한 모든 조합의 하위 많은 것을 얻을 수 있습니다.
- 모바일이 회문인지 확인하는 회문 기능이 있습니다.
- 모든 하위 하위 계층 (i, j)에 대해 함수를 호출합니다. 회문이면 디렉토리 변수에 저장됩니다.
- 다음 회문 부분을 찾고 있습니다.
- 마지막으로 많은 변수에 답이 있습니다.
문제 : 1.이 알고리즘은 O (n ^ 2) 시간에 실행됩니다.
알고 2 :
- 많은 것을 뒤집어 다른 배열에 저장하십시오.
- 이제 두 배열 사이에서 가장 일치하는 부분을 찾으십시오.
- 하지만 이것도 O (n ^ 2) 시간에 실행됩니다.
더 나은 시간에 실행되는 알고리즘을 생각할 수 있습니까? 가능하면 O (n) 시간
Manacher 's Algorithm 을 사용하여 가장 긴 회문을 사용할 수 있습니다 O(n)! 구현은 여기 와 여기 에서 장착 수 있습니다 .
입력의 경우 String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"올바른 출력을 찾습니다 1234567887654321.
Algo 2는 모든 것에서 작동하지 않을 수 있습니다. 다음은 꾸준한 "ABCDEFCBA"의 예입니다.
"ABC"및 "CBA"가있는 것은 아닙니다. "ABCFEDCBA"가됩니다. 가장 긴 일치하는 부분은 회문이 아닌 "ABC"입니다.
이 가장 긴 일치 하위 확장이 실행 시간이 O (n ^ 3) 인 회문인지 추가로 확인해야 할 수도 있습니다.
내가 문제를 이해하는 한, 우리는 중앙 색인 주위에서 회문을 사용하여 중앙의 오른쪽과 왼쪽 검색 범위를 둘 수 있습니다. 경계를 경계를 1 및 길이 -1로 할 수 있습니다. String의 최소 및 최대 경계에주의를 기울이면서 대칭 적 (오른쪽 및 왼쪽) 위치의 문자가 최대 상한 중심에 도달 할 때까지 각 중앙 위치에 대해 알고 있습니다.
외부 루프는 O (n) (최대 n-2 회 반복)이고 내부 while 루프는 O (n) (최대 약 (n / 2) -1 회 반복)
다음은 다른 사용자가 제공 한 예제를 사용하는 Java 구현입니다.
class LongestPalindrome {
/**
* @param input is a String input
* @return The longest palindrome found in the given input.
*/
public static String getLongestPalindrome(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex - 1; rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome.length() ? currentPalindrome : longestPalindrome;
leftIndex--; rightIndex++;
}
}
return longestPalindrome;
}
public static void main(String ... args) {
String str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
String longestPali = getLongestPalindrome(str);
System.out.println("String: " + str);
System.out.println("Longest Palindrome: " + longestPali);
}
}
이 결과는 다음과 가변적입니다.
marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321
정규식과 루비를 사용하면 다음과 같은 짧은 회문을 스캔 할 수 있습니다.
PROMPT> irb
>> s = "longtextwithranynarpalindrome"
=> "longtextwithranynarpalindrome"
>> s =~ /((\w)(\w)(\w)(\w)(\w)\6\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\w\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\5\4\3\2)/; p $1
nil
=> nil
>> s =~ /((\w)(\w)(\w)\w\4\3\2)/; p $1
"ranynar"
=> nil
최근 에이 질문을 예배합니다. 여기 내가 [결국] 생각 해낸 해결책이 있습니다. 해당 언어에서 매우 간단하기 때문에 JavaScript로했습니다.
기본 개념은 가능한 가장 작은 다중 문자 회문 (2 또는 3 문자)을 찾기 위해 현을 걷는 것입니다. 일단 양조의 경계를 확장하십시오. 그 길이가 현재 가장 긴 길이보다 길면 저장하고 따라 이동하십시오.
// This does the expanding bit.
function getsize(s, start, end) {
var count = 0, i, j;
for (i = start, j = end; i >= 0 && j < s.length; i--, j++) {
if (s[i] !== s[j]) {
return count;
}
count = j - i + 1; // keeps track of how big the palindrome is
}
return count;
}
function getBiggestPalindrome(s) {
// test for simple cases
if (s === null || s === '') { return 0; }
if (s.length === 1) { return 1; }
var longest = 1;
for (var i = 0; i < s.length - 1; i++) {
var c = s[i]; // the current letter
var l; // length of the palindrome
if (s[i] === s[i+1]) { // this is a 2 letter palindrome
l = getsize(s, i, i+1);
}
if (i+2 < s.length && s[i] === s[i+2]) { // 3 letter palindrome
l = getsize(s, i+1, i+1);
}
if (l > longest) { longest = l; }
}
return longest;
}
이것은 확실히 정리하고 약간 더 최적화 할 수있는 상황 시나리오 (같은 문자의 많은 경우)를 사용할 수있는 상황에서 꽤 좋은 성능을 가져옵니다.
안녕 여기에서 가장 긴 회문을 찾는 코드가 있습니다. 알고리즘을 이해하려는 다음 링크를 참조하십시오. http://stevekrenzel.com/articles/longest-palnidrome
사용 된 테스트 데이터는 HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE입니다.
//Function GetPalindromeString
public static string GetPalindromeString(string theInputString)
{
int j = 0;
int k = 0;
string aPalindrome = string.Empty;
string aLongestPalindrome = string.Empty ;
for (int i = 1; i < theInputString.Length; i++)
{
k = i + 1;
j = i - 1;
while (j >= 0 && k < theInputString.Length)
{
if (theInputString[j] != theInputString[k])
{
break;
}
else
{
j--;
k++;
}
aPalindrome = theInputString.Substring(j + 1, k - j - 1);
if (aPalindrome.Length > aLongestPalindrome.Length)
{
aLongestPalindrome = aPalindrome;
}
}
}
return aLongestPalindrome;
}
이 주제에 대한 Wikipedia 가이드 를 참조하십시오 . 아래 기사에서 선형 O (n) 솔루션에 대한 샘플 Manacher의 알고리즘 Java 구현 :
import java.util.Arrays; public class ManachersAlgorithm {public static String findLongestPalindrome (String s) {if (s == null || s.length () == 0) return "";
char[] s2 = addBoundaries(s.toCharArray()); int[] p = new int[s2.length]; int c = 0, r = 0; // Here the first element in s2 has been processed. int m = 0, n = 0; // The walking indices to compare if two elements are the same for (int i = 1; i<s2.length; i++) { if (i>r) { p[i] = 0; m = i-1; n = i+1; } else { int i2 = c*2-i; if (p[i2]<(r-i)) { p[i] = p[i2]; m = -1; // This signals bypassing the while loop below. } else { p[i] = r-i; n = r+1; m = i*2-n; } } while (m>=0 && n<s2.length && s2[m]==s2[n]) { p[i]++; m--; n++; } if ((i+p[i])>r) { c = i; r = i+p[i]; } } int len = 0; c = 0; for (int i = 1; i<s2.length; i++) { if (len<p[i]) { len = p[i]; c = i; } } char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1); return String.valueOf(removeBoundaries(ss)); } private static char[] addBoundaries(char[] cs) { if (cs==null || cs.length==0) return "||".toCharArray(); char[] cs2 = new char[cs.length*2+1]; for (int i = 0; i<(cs2.length-1); i = i+2) { cs2[i] = '|'; cs2[i+1] = cs[i/2]; } cs2[cs2.length-1] = '|'; return cs2; } private static char[] removeBoundaries(char[] cs) { if (cs==null || cs.length<3) return "".toCharArray(); char[] cs2 = new char[(cs.length-1)/2]; for (int i = 0; i<cs2.length; i++) { cs2[i] = cs[i*2+1]; } return cs2; } }
Regexp무차별 대입을 피하는 효율적인 솔루션
전체 길이로 시작하여 2 자까지 작동하며 일치하는 즉시 존재합니다.
"abaccddccefe"표현식의 정규 경우 ccddcc.
(.) (.) (.) (.) (.) (.) (\ 6) (\ 5) (\ 4) (\ 3) (\ 2) (\ 1)
(.) (.) (. ) (.) (.) (.) (\ 5) (\ 4) (\ 3) (\ 2) (\ 1)
(.) (.) (.) (.) (.) (\ 5) ( \ 4) (\ 3) (\ 2) (\ 1)
(.) (.) (.) (.) (.) (\ 4) (\ 3) (\ 2) (\ 1)
(.) ( .) (.) (.) (\ 4) (\ 3) (\ 2) (\ 1)
(.) (.) (.) (.) (\ 3) (\ 2) (\ 1)
(. ) (.) (.) (\ 3) (\ 2) (\ 1)
Dim strTest
wscript.echo Palindrome("abaccddccefe")
Sub Test()
Dim strTest
MsgBox Palindrome("abaccddccefe")
End Sub
함수
Function Palindrome(strIn)
Set objRegex = CreateObject("vbscript.regexp")
For lngCnt1 = Len(strIn) To 2 Step -1
lngCnt = lngCnt1 \ 2
strPal = vbNullString
For lngCnt2 = lngCnt To 1 Step -1
strPal = strPal & "(\" & lngCnt2 & ")"
Next
If lngCnt1 Mod 2 = 1 Then strPal = "(.)" & strPal
With objRegex
.Pattern = Replace(Space(lngCnt), Chr(32), "(.)") & strPal
If .Test(strIn) Then
Palindrome = .Execute(strIn)(0)
Exit For
End If
End With
Next
End Function
나는 호기심, 간단하고 자명 한 HTH로 다음 Java 프로그램을 작성했습니다. 감사합니다.
/**
*
* @author sanhn
*/
public class CheckPalindrome {
private static String max_string = "";
public static void checkSubString(String s){
System.out.println("Got string is "+s);
for(int i=1;i<=s.length();i++){
StringBuilder s1 = new StringBuilder(s.substring(0,i));
StringBuilder s2 = new StringBuilder(s.substring(0,i));
s2.reverse();
if(s1.toString().equals(s2.toString())){
if(max_string.length()<=s1.length()){
max_string = s1.toString();
System.out.println("tmp max is "+max_string);
}
}
}
}
public static void main(String[] args){
String s="HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE";
for(int i=0; i<s.length(); i++)
checkSubString(s.substring(i, s.length()));
System.out.println("Max string is "+max_string);
}
}
public static void main(String[] args) {
System.out.println(longestPalindromeString("9912333321456"));
}
static public String intermediatePalindrome(String s, int left, int right) {
if (left > right) return null;
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return s.substring(left + 1, right);
}
public static String longestPalindromeString(String s) {
if (s == null) return null;
String longest = s.substring(0, 1);
for (int i = 0; i < s.length() - 1; i++) {
//odd cases like 121
String palindrome = intermediatePalindrome(s, i, i);
if (palindrome.length() > longest.length()) {
longest = palindrome;
}
//even cases like 1221
palindrome = intermediatePalindrome(s, i, i + 1);
if (palindrome.length() > longest.length()) {
longest = palindrome;
}
}
return longest;
}
꾸러미 "HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE"; 짝수와 홀수 친구에게도 효과가있을 것입니다. Mohit에 감사드립니다!
네임 스페이스 std 사용;
string largestPal(string input_str)
{
string isPal = "";
string largest = "";
int j, k;
for(int i = 0; i < input_str.length() - 1; ++i)
{
k = i + 1;
j = i - 1;
// starting a new interation
// check to see if even pal
if(j >= 0 && k < input_str.length()) {
if(input_str[i] == input_str[j])
j--;
else if(input_str[i] == input_str[j]) {
k++;
}
}
while(j >= 0 && k < input_str.length())
{
if(input_str[j] != input_str[k])
break;
else
{
j--;
k++;
}
isPal = input_str.substr(j + 1, k - j - 1);
if(isPal.length() > largest.length()) {
largest = isPal;
}
}
}
return largest;
}
다음 코드는 짝수 길이와 홀수 길이에 대해 Palidrom을 계산합니다.
최상의 솔루션은 두 경우 모두에서 작동합니다.
HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE
private static String getLongestPalindrome(String string) {
String odd = getLongestPalindromeOdd(string);
String even = getLongestPalindromeEven(string);
return (odd.length() > even.length() ? odd : even);
}
public static String getLongestPalindromeOdd(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex;
rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome
.length() ? currentPalindrome : longestPalindrome;
leftIndex--;
rightIndex++;
}
}
return longestPalindrome;
}
public static String getLongestPalindromeEven(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex - 1;
rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome
.length() ? currentPalindrome : longestPalindrome;
leftIndex--;
rightIndex++;
}
}
return longestPalindrome;
}
- 구분 기호를 사용하여 각 문자를 구분 숫자 수정 [홀수 및 짝수 수정]
- 취급하는 각 캐릭터 주변의 회문을 찾습니다.
이것을 사용하여 모든 길이의 모든 회문을 사용할 수 있습니다.
샘플 :
단어 = abcdcbc
modifiedString = a # b # c # d # c # b # c
palinCount = 1010105010301
가장 긴 회 문의 길이 = 5;
가장 긴 회문 = bcdcb
public class MyLongestPalindrome {
static String word;
static int wordlength;
static int highestcount = 0;
static int newlength;
static char[] modifiedString; // stores modified string
static int[] palinCount; // stores palindrome length at each position
static char pound = '#';
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
System.out.println("Enter String : ");
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader bfr = new BufferedReader(isr);
word = bfr.readLine();
wordlength = word.length();
newlength = (wordlength * 2) - 1;
convert();
findpalindrome();
display();
}
// Inserting # in string
public static void convert() {
modifiedString = new char[newlength];
int j = 0;
int i;
for (i = 0; i < wordlength - 1; i++) {
modifiedString[j++] = word.charAt(i);
modifiedString[j++] = pound;
}
modifiedString[j] = word.charAt(i);
}
// display all palindromes of highest length
public static void display() {
String palindrome;
String s = new String(modifiedString);
System.out.println("Length of longest palindrome = " + highestcount);
for (int i = 0; i < newlength; i++) {
if (palinCount[i] == highestcount) {
palindrome = s.substring(i - (highestcount - 1), i
+ (highestcount));
i = i + (highestcount - 1);
palindrome = palindrome.replace("#", "");
System.out.println(palindrome);
}
}
}
// populate palinCount with length of palindrome string at each position
public static void findpalindrome() {
int left, right, count;
palinCount = new int[newlength];
palinCount[0] = 1;
palinCount[newlength - 1] = 1;
for (int i = 1; i < newlength - 1; i++) {
count = 0;
left = i - 1;
right = i + 1;
;
if (modifiedString[i] != pound)
count++;
while (left >= 0 && right < newlength) {
if (modifiedString[left] == modifiedString[right]) {
if (modifiedString[left] != pound)
count = count + 2;
left--;
right++;
} else
break;
}
palinCount[i] = count;
highestcount = count > highestcount ? count : highestcount;
}
}
}
주어진 최소에서 가장 긴 회문을 반환합니다.
-(BOOL)isPalindromString:(NSString *)strInput
{
if(strInput.length<=1){
return NO;
}
int halfLenth = (int)strInput.length/2;
BOOL isPalindrom = YES;
for(NSInteger i=0; i<halfLenth; i++){
char a = [strInput characterAtIndex:i];
char b = [strInput characterAtIndex:(strInput.length-1)-i];
if(a != b){
isPalindrom = NO;
break;
}
}
NSLog(@"-%@- IS Plaindrom %@",strInput,(isPalindrom ? @"YES" : @"NO"));
return isPalindrom;
}
-(NSString *)longestPalindrom:(NSString *)strInput
{
if(strInput.length<=1){
return @"";
}
NSString *strMaxPalindrom = @"";
for(int i = 0; i<strInput.length ; i++){
for(int j = i; j<strInput.length ; j++){
NSString *strSub = [strInput substringWithRange:NSMakeRange(i, strInput.length-j)];
if([self isPalindromString:strSub]){
if(strSub.length>strMaxPalindrom.length){
strMaxPalindrom = strSub;
}
}
}
}
NSLog(@"-Max - %@",strMaxPalindrom);
return strMaxPalindrom;
}
-(void)test
{
[self longestPalindrom:@"abcccbadeed"];
}
== 출력 ===
입력 : abcccde 출력 : ccc
입력 : abcccbd 출력 : bcccb
입력 : abedccde 출력 : edccde
입력 : abcccdeed 출력 : deed
입력 : abcccbadeed 출력 : abcccba
다음은 자바 펼쳐로 구현 된 것입니다.
var longestPalindromeLength = 0;
var longestPalindrome = ''
function isThisAPalidrome(word){
var reverse = word.split('').reverse().join('')
return word == reverse
}
function findTheLongest(word){ // takes a word of your choice
for(var i = 0; i < word.length; i++){ // iterates over each character
var wordMinusOneFromBeginning = word.substr(i, word.length) // for each letter, create the word minus the first char
for(var j = wordMinusOneFromBeginning.length; j > 0; j--){ // for the length of the word minus the first char
var wordMinusOneFromEnding = wordMinusOneFromBeginning.substr(0, j) // create a word minus the end character
if(wordMinusOneFromEnding <= 0) // make sure the value is more that 0,
continue // if more than zero, proced to next if statement
if(isThisAPalidrome(wordMinusOneFromEnding)){ // check if the word minus the first character, minus the last character = a plaindorme
if(wordMinusOneFromEnding.length > longestPalindromeLength){ // if it is
longestPalindromeLength = wordMinusOneFromEnding.length; // save its length
longestPalindrome = wordMinusOneFromEnding // and save the string itself
} // exit the statement that updates the longest palidrome
} // exit the stament that checks for a palidrome
} // exit the loop that goes backwards and takes a letter off the ending
} // exit the loop that goes forward and takes off the beginning letter
return console.log('heres the longest string: ' + longestPalindrome
+ ' its ' + longestPalindromeLength + ' charachters in length'); // return the longest palidrome! :)
}
findTheLongest('bananas');선형 솔루션의 경우 Manacher의 알고리즘을 사용할 수 있습니다. Gusfield의 Algorithm이라는 또 다른 알고리즘이 있고 아래는 java의 코드입니다.
public class Solution {
char[] temp;
public int match(int a, int b,int len){
int i = 0;
while (a-i>=0 && b+i<len && temp[a-i] == temp[b+i]) i++;
return i;
}
public String longestPalindrome(String s) {
//This makes use of the assumption that the string has not more than 1000 characters.
temp=new char[1001*2];
int[] z=new int[1001 * 2];
int L=0, R=0;
int len=s.length();
for(int i=0;i<len*2+1;i++){
temp[i]='.';
}
for(int i=0;i<len;++i){
temp[i*2+1] = s.charAt(i);
}
z[0]=1;
len=len*2+1;
for(int i=0;i<len;i++){
int ii = L - (i - L);
int n = R + 1 - i;
if (i > R)
{
z[i] = match(i, i,len);
L = i;
R = i + z[i] - 1;
}
else if (z[ii] == n)
{
z[i] = n + match(i-n, i+n,len);
L = i;
R = i + z[i] - 1;
}
else
{
z[i] = (z[ii]<= n)? z[ii]:n;
}
}
int n = 0, p = 0;
for (int i=0; i<len; ++i)
if (z[i] > n)
n = z[p = i];
StringBuilder result=new StringBuilder();
for (int i=p-z[p]+1; i<=p+z[p]-1; ++i)
if(temp[i]!='.')
result.append(String.valueOf(temp[i]));
return result.toString();
}
}
내 블로그 에서 최고의 O (n ^ 2) 솔루션 또는 Manacher의 알고리즘과 같은 다른 솔루션에 대해 자세히 알아볼 수 있습니다 .
여기에 논리를 작성했습니다 :)
public class palindromeClass{
public static String longestPalindromeString(String in) {
char[] input = in.toCharArray();
int longestPalindromeStart = 0;
int longestPalindromeEnd = 0;
for (int mid = 0; mid < input.length; mid++) {
// for odd palindrome case like 14341, 3 will be the mid
int left = mid-1;
int right = mid+1;
// we need to move in the left and right side by 1 place till they reach the end
while (left >= 0 && right < input.length) {
// below check to find out if its a palindrome
if (input[left] == input[right]) {
// update global indexes only if this is the longest one till now
if (right - left > longestPalindromeEnd
- longestPalindromeStart) {
longestPalindromeStart = left;
longestPalindromeEnd = right;
}
}
else
break;
left--;
right++;
}
// for even palindrome, we need to have similar logic with mid size 2
// for that we will start right from one extra place
left = mid;
right = mid + 1;// for example 12333321 when we choose 33 as mid
while (left >= 0 && right < input.length)
{
if (input[left] == input[right]) {
if (right - left > longestPalindromeEnd
- longestPalindromeStart) {
longestPalindromeStart = left;
longestPalindromeEnd = right;
}
}
else
break;
left--;
right++;
}
}
// we have the start and end indexes for longest palindrome now
return in.substring(longestPalindromeStart, longestPalindromeEnd + 1);
}
public static void main(String args[]){
System.out.println(longestPalindromeString("HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE"));
}
}
이 솔루션은 O (n ^ 2) 복잡도입니다. O (1)은 공간 스케치입니다.
public class longestPalindromeInAString {
public static void main(String[] args) {
String a = "xyMADAMpRACECARwl";
String res = "";
//String longest = a.substring(0,1);
//System.out.println("longest => " +longest);
for (int i = 0; i < a.length(); i++) {
String temp = helper(a,i,i);//even palindrome
if(temp.length() > res.length()) {res = temp ;}
temp = helper(a,i,i+1);// odd length palindrome
if(temp.length() > res.length()) { res = temp ;}
}//for
System.out.println(res);
System.out.println("length of " + res + " is " + res.length());
}
private static String helper(String a, int left, int right) {
while(left>= 0 && right <= a.length() -1 && a.charAt(left) == a.charAt(right)) {
left-- ;right++ ;
}
String curr = a.substring(left + 1 , right);
System.out.println("curr =>" +curr);
return curr ;
}
}
#longest palindrome
s='HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE'
out1=[]
def substring(x):
for i in range(len(x)):
a=x[i:]
b=x[:-i]
out1.append(a)
out1.append(b)
return out1
for i in range(len(s)):
substring(s[i:])
final=set([item for item in out1 if len(item)>2])
final
palind={item:len(item) for item in final if item==item[::-1]}
print(palind)
sorted(palind.items(),reverse=True, key=lambda x: x[1])[0]{ 'DED': 3, '123456789987654321': 18, '67899876': 8, 'ABCDEDCBA': 9, '456789987654': 12, '34567899876543': 14, 'BCDEDCB': 7, 'ABA': 3, ' 5678998765 ': 10,'2345678998765432 ': 16,'CDEDC ': 5,'789987 ': 6,'8998 ': 4} ('123456789987654321 ', 18)
내 알고리즘은 다음과 가변합니다.
1) 현재 중심을 첫 글자로 설정
2) 현재 중심 주변의 최대 회문을 장비 할 때 동시에 동시에 오른쪽으로 확장
3) 새로운 회문이 이전 회문보다 크면 업데이트하십시오.
4) 현재 중심을 다음 문자로 설정
5) 단계를 반복합니다. 2) ~ 4) 단계를 반복합니다.
이 O (n)에서 실행됩니다.
도움이되기를 바랍니다.
참조 : Wikipedia.com
내가 얼마나 최고의 알고리즘, 내가 O (N)
import java.util.Arrays;
public class ManachersAlgorithm {
public static String findLongestPalindrome(String s) {
if (s==null || s.length()==0)
return "";
char[] s2 = addBoundaries(s.toCharArray());
int[] p = new int[s2.length];
int c = 0, r = 0; // Here the first element in s2 has been processed.
int m = 0, n = 0; // The walking indices to compare if two elements are the same
for (int i = 1; i<s2.length; i++) {
if (i>r) {
p[i] = 0; m = i-1; n = i+1;
} else {
int i2 = c*2-i;
if (p[i2]<(r-i)) {
p[i] = p[i2];
m = -1; // This signals bypassing the while loop below.
} else {
p[i] = r-i;
n = r+1; m = i*2-n;
}
}
while (m>=0 && n<s2.length && s2[m]==s2[n]) {
p[i]++; m--; n++;
}
if ((i+p[i])>r) {
c = i; r = i+p[i];
}
}
int len = 0; c = 0;
for (int i = 1; i<s2.length; i++) {
if (len<p[i]) {
len = p[i]; c = i;
}
}
char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
return String.valueOf(removeBoundaries(ss));
}
private static char[] addBoundaries(char[] cs) {
if (cs==null || cs.length==0)
return "||".toCharArray();
char[] cs2 = new char[cs.length*2+1];
for (int i = 0; i<(cs2.length-1); i = i+2) {
cs2[i] = '|';
cs2[i+1] = cs[i/2];
}
cs2[cs2.length-1] = '|';
return cs2;
}
private static char[] removeBoundaries(char[] cs) {
if (cs==null || cs.length<3)
return "".toCharArray();
char[] cs2 = new char[(cs.length-1)/2];
for (int i = 0; i<cs2.length; i++) {
cs2[i] = cs[i*2+1];
}
return cs2;
}
}
내 솔루션은 다음과 달라집니다.
static string GetPolyndrom(string str)
{
string Longest = "";
for (int i = 0; i < str.Length; i++)
{
if ((str.Length - 1 - i) < Longest.Length)
{
break;
}
for (int j = str.Length - 1; j > i; j--)
{
string str2 = str.Substring(i, j - i + 1);
if (str2.Length > Longest.Length)
{
if (str2 == str2.Reverse())
{
Longest = str2;
}
}
else
{
break;
}
}
}
return Longest;
}
반응형
'IT' 카테고리의 다른 글
| 단일 페이지 애플리케이션을 구축하기위한 JavaScript 프레임 워크 (0) | 2020.08.18 |
|---|---|
| JSON 값에 여러 줄 다수가 있습니까? (0) | 2020.08.18 |
| C는 이니셜 라이저에서 [N… M]은 무엇을 의미하고 있습니까? (0) | 2020.08.18 |
| arrayfun은 matlab의 명시 적 루프보다 훨씬 느릴 수 있습니다. (0) | 2020.08.18 |
| Scala의 "flatmap that s ***"관용적 표현은 어디에서 왔습니까? (0) | 2020.08.16 |