Schreiben Sie eine Funktion, die das längste Palindrom in einer bestimmten Zeichenfolge zurückgibt

101

zB "ccddcc" in der Zeichenfolge "abaccddccefe"

Ich dachte an eine Lösung, aber sie läuft in O (n ^ 2) Zeit

Algo 1:

Schritte: Es ist eine Brute-Force-Methode

  1. Haben Sie 2 for-Schleifen
    für i = 1 bis i kleiner als array.length -1
    für j = i + 1 bis j kleiner als array.length
  2. Auf diese Weise können Sie Teilstrings jeder möglichen Kombination aus dem Array abrufen
  3. Haben Sie eine Palindrom-Funktion, die prüft, ob eine Zeichenfolge Palindrom ist
  4. Rufen Sie diese Funktion für jeden Teilstring (i, j) auf, wenn es sich um ein Palindrom handelt, und speichern Sie sie in einer Zeichenfolgenvariablen
  5. Wenn Sie den nächsten Palindrom-Teilstring finden und dieser größer als der aktuelle ist, ersetzen Sie ihn durch den aktuellen.
  6. Schließlich hat Ihre Zeichenfolgenvariable die Antwort

Probleme: 1. Dieses Algo läuft in O (n ^ 2) Zeit.

Algo 2:

  1. Kehren Sie die Zeichenfolge um und speichern Sie sie in einem anderen Array
  2. Suchen Sie nun den größten passenden Teilstring zwischen beiden Arrays
  3. Aber auch dies läuft in O (n ^ 2) Zeit

Könnt ihr euch einen Algo vorstellen, der in einer besseren Zeit läuft? Wenn möglich O (n) Zeit

Lerner
quelle
42
Ich denke, die erste besteht O(n^2)darin, die Teilzeichenfolgen * O(n)zu überprüfen, ob es sich um Palindrome handelt O(n^3).
Skylar Saveland
Was wäre, wenn ich wüsste, dass ich mit Palindrom arbeite und meine Zeichenfolgen als zwei Hälften speichere, und wenn ich dann Java verwenden würde, würde ich O (1) auf die Funktion prüfen lassen?
viki.omega9
10
Das zweite Algo ist richtig? Was ist mit der Zeichenfolge: "abcdecba". Der größte passende Teilstring ist ("abcdecba" vs. "abcedcba"): "abc" oder "cba". Beide sind jedoch keine Palindrome.
Yarneo
@Learner, nur neugierig, in Ihren Schritten über welches Array beziehen Sie sich in Ihren for-Schleifen? Beziehen Sie sich nach Array auf die Zeichenfolge? String-Länge?
Zolt
1
für diejenigen, die eine Antwort mit O (n ^ 2) suchen
geeksforgeeks.org/longest-palindrome-substring-set-1

Antworten:

76

Sie können die die längste Palindrom mit finden Manacher-Algorithmus in der O(n)Zeit! Die Umsetzung finden Sie hier und hier .

Für die Eingabe String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"findet es die richtige Ausgabe 1234567887654321.

AnujKu
quelle
3
Ich verstehe nicht, wie linear das ist. Ich sehe eine whileeingebettete formit einer Begrenzung, die der äußeren Schleife ähnlich zu sein scheint.
v.oddou
9

Der Algo 2 funktioniert möglicherweise nicht für alle Zeichenfolgen. Hier ist ein Beispiel für eine solche Zeichenfolge "ABCDEFCBA".

Nicht dass der String "ABC" und "CBA" als Teilzeichenfolge hat. Wenn Sie die ursprüngliche Zeichenfolge umkehren, ist dies "ABCFEDCBA". und der am längsten passende Teilstring ist "ABC", was kein Palindrom ist.

Möglicherweise müssen Sie zusätzlich prüfen, ob es sich bei diesem am längsten passenden Teilstring tatsächlich um ein Palindrom handelt, das die Laufzeit von O (n ^ 3) hat.

VCB
quelle
2
Es ist wichtig zu beachten, dass Algo 2 für das "Palindrom mit der längsten übereinstimmenden Teilsequenz" funktionieren sollte. Dies ist ein häufiges Algorithmusproblem, bei dem die Teilsequenzzeichen auch innerhalb der Zeichenfolge getrennt werden können. Die am längsten übereinstimmende Teilsequenz (einschließlich Zeichentrennungen) zwischen den beiden obigen Zeichenfolgen ist beispielsweise "ABCFCBA", das auch ein Palindrom ist :) Hier ein Link, der das LCS-Problem beschreibt: ics.uci.edu/~eppstein/161/960229.html
Jake Drew
5

Soweit ich das Problem verstanden habe, können wir Palindrome um einen Mittelindex finden und unsere Suche in beide Richtungen rechts und links vom Zentrum überspannen. Wenn wir wissen, dass sich an den Ecken der Eingabe kein Palindrom befindet, können wir die Grenzen auf 1 und Länge-1 setzen. Während wir auf die minimalen und maximalen Grenzen des Strings achten, überprüfen wir, ob die Zeichen an den Positionen der symmetrischen Indizes (rechts und links) für jede zentrale Position gleich sind, bis wir unsere maximale obere Grenze erreichen.

Die äußere Schleife ist O (n) (max n-2 Iterationen) und die innere while-Schleife ist O (n) (max um (n / 2) - 1 Iterationen)

Hier ist meine Java-Implementierung anhand des Beispiels anderer Benutzer.

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);
    }
}

Die Ausgabe davon ist die folgende:

marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321
Marcello de Sales
quelle
6
Wenn ich "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" gebe, funktioniert es nicht, aber die Antwort sollte 1234567887654321
Elbek
1
@j_random_hacker nein, das ist eine der quadratischen Lösungen. Es wird hier als behandeltexpandAroundCenter .
v.oddou
@ v.oddou: Du hast absolut Recht und ich weiß nicht, wie ich zu O (n ^ 3) gekommen bin, da es nur 2 verschachtelte Schleifen gibt! Ich werde diesen falschen Kommentar löschen ... Aber ich habe auch bemerkt, dass diese Lösung ein Problem hat, das ich in einen separaten Kommentar einfügen werde, damit der Autor es hoffentlich bemerkt.
j_random_hacker
Meine frühere Behauptung der O (n ^ 3) -Zeitkomplexität war falsch (danke @ v.oddou für den Hinweis!), Aber es gibt noch ein anderes Problem: Dieser Code berücksichtigt keine Palindrome mit gerader Länge. Dies könnte durch Hinzufügen einer zweiten, sehr ähnlichen äußeren Schleife (auch O (n ^ 2), damit die Komplexität der O (n ^ 2) -Zeit nicht beeinflusst wird) behoben werden, die Palindrome um jede der n-1-Positionen zwischen jeder erweitert Zeichenpaar. +2 wenn Sie reparieren :)
j_random_hacker
2

Mit Regex und Ruby können Sie nach kurzen Palindromen wie diesen suchen:

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
neoneye
quelle
2

Ich habe das folgende Java-Programm aus Neugier, einfacher und selbsterklärender HTH geschrieben. Vielen Dank.

/**
 *
 * @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);
    }
}
Cleonjoys
quelle
1

Diese Frage wurde mir kürzlich gestellt. Hier ist die Lösung, die ich [irgendwann] gefunden habe. Ich habe es in JavaScript gemacht, weil es in dieser Sprache ziemlich einfach ist.

Das Grundkonzept besteht darin, dass Sie über die Zeichenfolge gehen und nach dem kleinstmöglichen Palindrom mit mehreren Zeichen suchen (entweder mit zwei oder drei Zeichen). Wenn Sie das haben, erweitern Sie die Ränder auf beiden Seiten, bis es kein Palindrom mehr ist. Wenn diese Länge länger als die aktuell längste ist, speichern Sie sie und gehen Sie weiter.

// 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;
}

Dies könnte definitiv etwas mehr bereinigt und optimiert werden, aber es sollte in allen außer dem Worst-Case-Szenario (eine Zeichenfolge aus demselben Buchstaben) eine ziemlich gute Leistung haben.

Swilliams
quelle
1
Ich dachte ursprünglich, das OP-Algo Nr. 1 sei O (n ^ 2) -Zeit, aber es ist tatsächlich ohne Kopf O (n ^ 3). Obwohl Ihr Algorithmus es nicht bis zur erreichbaren O (n) -Grenze schafft, Es ist immer noch eine Verbesserung.
j_random_hacker
1
Sie nennen dies "unkompliziert", aber es ist voll von i j l s ifund Zustand Wartung. Multi Return Points, Edge Cases ...
v.oddou
1

Hallo, hier ist mein Code, um das längste Palindrom in der Zeichenfolge zu finden. Bitte beziehen Sie sich auf den folgenden Link, um den Algorithmus zu verstehen: http://stevekrenzel.com/articles/longest-palnidrome

Die verwendeten Testdaten sind 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;     
  }
Mohit Bhandari
quelle
Ich bin mir nicht sicher, ob dies mit Palindromen mit gleichmäßiger Länge funktioniert ... können Sie das bestätigen?
st0le
Dies funktioniert auch für Palindrome. Sie können dieses Programm ausführen und mich wissen lassen, wenn es nicht für Sie funktioniert. Zum Verständnis des Algorithmus verweisen Sie bitte
Mohit Bhandari
@ st0le: Diese Logik funktioniert nicht einmal für Palindrome, aber sie könnte für sogar Palindrome angepasst werden. Bedauere mich sehr für das frühere Kommnent. Ich habe die Logik und werde sie in ein paar Tagen aktualisieren, sobald ich Zeit habe.
Mohit Bhandari
Lies deinen vorherigen Kommentar bis heute nie ... du hast mich das letzte Mal nicht angesprochen ... nimm dir Zeit, es war nur eine Beobachtung.
st0le
2
Ich dachte ursprünglich, das OP-Algo Nr. 1 sei O (n ^ 2) -Zeit, aber es ist tatsächlich O (n ^ 3) ohne Kopf. Obwohl Ihr Algorithmus es nicht bis zur erreichbaren O (n) -Grenze schafft, Es ist immer noch eine Verbesserung.
j_random_hacker
1

Siehe Wikipedia-Artikel zu diesem Thema. Beispiel für die Java-Implementierung des Manacher-Algorithmus für eine lineare O (n) -Lösung aus dem folgenden Artikel:

import java.util.Arrays; öffentliche Klasse 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;   }     }

1

Eine effiziente RegexpLösung, die rohe Gewalt vermeidet

Beginnt mit der gesamten Stringlänge und arbeitet abwärts bis zu 2 Zeichen, existiert sobald eine Übereinstimmung hergestellt ist

Für "abaccddccefe"die Regexp-Tests 7 Übereinstimmungen vor der Rückkehr 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

Funktion

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

@ DickKusleika können Sie bitte meinen Kommentar unter dailydoseofexcel.com/archives/2016/01/14/… mit dem überarbeiteten Code oben aktualisieren . Thx
brettdj

1
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;
    }

0

Versuchen Sie die Zeichenfolge - "HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE"; Es sollte für gerade und ungerade Freunde funktionieren. Vielen Dank an Mohit!

Verwenden des Namespace 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;
}

2
Dies macht fast Dinge in O (n ^ 2) Zeit. Warum isPaleine O (n) -Operation erstellen, nur um ihre Länge zu messen? Es hat auch einen fehlerhaften Versuch, sogar Palindrome zu handhaben. Bei gleichmäßigen Palindrom-Fehlern: else if(input_str[i] == input_str[j])Kann niemals erfolgreich sein, da derselbe Test in der vorherigen ifAnweisung fehlgeschlagen sein muss . und es ist sowieso fehlerhaft, weil man nicht einfach anhand von 2 Zeichen im Abstand von 2 Positionen erkennen kann, ob man ein gerades oder ein ungerades Palindrom betrachtet (siehe AAAund AAAA).
j_random_hacker

0

Der folgende Code berechnet Palidrom für Zeichenfolgen mit gerader und ungerader Länge.

Nicht die beste Lösung, funktioniert aber in beiden Fällen

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;
}

0
  1. Ändern Sie die Zeichenfolge, um jedes Zeichen mithilfe eines Trennzeichens zu trennen [dies beinhaltet ungerade und gerade Palindrome]
  2. Finden Sie Palindrome um jeden Charakter, der ihn als Zentrum behandelt

Damit können wir alle Palindrome aller Länge finden.

Stichprobe :

word = abcdcbc

modifiziertString = a # b # c # d # c # b # c

palinCount = 1010105010301

Länge des längsten Palindroms = 5;

längstes Palindrom = bcdcb

öffentliche Klasse 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;

    }

}

}}

nnc
quelle
0

Dies gibt die längste Palindrom-Zeichenfolge von der angegebenen Zeichenfolge zurück

-(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"];
}

== AUSGABE ===

Eingabe: abcccde Ausgabe: ccc

Eingabe: abcccbd Ausgabe: bcccb

Eingabe: abedccde Ausgabe: edccde

Eingabe: abcccdeed Ausgabe: Tat

Eingabe: abcccbadeed Ausgabe: abcccba

Kiran Patel
quelle
0

Hier ist eine Implementierung in Javascript:

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');

alex bennett
quelle
Ich weiß nicht, warum dies abgelehnt wurde - funktioniert wie ein Zauber. Ich habe ein Interview mit CA-Technologien geführt.
Alex Bennett
0

Für eine lineare Lösung können Sie den Manacher-Algorithmus verwenden. Es gibt einen anderen Algorithmus namens Gusfields Algorithmus, und unten ist der Code in 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();  
    }  
}  

Weitere Informationen zu anderen Lösungen wie der besten O (n ^ 2) -Lösung oder dem Manacher-Algorithmus finden Sie in meinem eigenen Blog .

Spurenformel
quelle
0

Hier habe ich eine Logik geschrieben, versuche es :)

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"));
}

}
kalt
quelle
Dies gibt das gesamte Palindrom in der Saite nicht nur das längste
Vivek Mishra
0

Diese Lösung ist von O (n ^ 2) -Komplexität. O (1) ist die Raumkomplexität.

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 ;
        }

    }
Soudipta Dutta
quelle
0

#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)

aschiges Bansal
quelle
-1

Hier ist mein Algorithmus:

1) Stellen Sie die aktuelle Mitte als ersten Buchstaben ein

2) Erweitern Sie gleichzeitig nach links und rechts, bis Sie das maximale Palindrom um das aktuelle Zentrum finden

3) Wenn das gefundene Palindrom größer als das vorherige Palindrom ist, aktualisieren Sie es

4) Stellen Sie die aktuelle Mitte als nächsten Buchstaben ein

5) Wiederholen Sie die Schritte 2) bis 4) für alle Buchstaben in der Zeichenfolge

Dies läuft in O (n).

Ich hoffe es hilft.

Spinne
quelle
5
Betrachten Sie die Zeichenfolge "aaaaaa". Dies läuft in O (n ^ 2) unter Verwendung Ihres Algorithmus.
Paislee
1
Ich dachte ursprünglich, das OP-Algo Nr. 1 sei O (n ^ 2) -Zeit, aber es ist tatsächlich O (n ^ 3) ohne Kopf. Obwohl Ihr Algorithmus es nicht bis zur erreichbaren O (n) -Grenze schafft, Es ist immer noch eine Verbesserung.
j_random_hacker
Das ist die klassische N2-Erweiterungslösung. ABER, das kommt der Lösung von Manacher nahe, wie in diesem Video erläutert: youtube.com/watch?v=V-sEwsca1ak Der Unterschied ist Punkt 4. Manacher verwendet Informationen wieder, um zu vermeiden, dass bereits gescannte Briefe erneut gescannt werden.
v.oddou
-2

Referenz: Wikipedia.com

Der beste Algorithmus, den ich je gefunden habe, mit der Komplexität 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;
  }    
}
Sazzad Hissain Khan
quelle
-5

Meine Lösung ist:

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;
}
Tomer Keisar
quelle
1
Dies dauert aufgrund der Operationen und string-equality ( ) kubische Zeit in der Zeichenfolgenlänge . Es ist im Grunde identisch mit dem OP Algo # 1. Substring()==
j_random_hacker