Écrire une fonction qui retourne le plus long palindrome dans une chaîne
E. g "ccddcc" dans la chaîne "abaccddcccefe "
j'ai pensé à une solution mais elle fonctionne dans le temps O (N^2)
Algo 1:
Steps: Sa force brute de la méthode
- Ont 2 pour les boucles
pour i = 1 à i moins de tableau.longueur -1
pour j=i+1 à j moins de tableau.longueur - par ici. peut obtenir la soustraction de toutes les combinaisons possibles à partir du tableau
- ont une fonction palindrome qui vérifie si une chaîne est palindrome
- donc pour chaque substrat (i,j) appelez cette fonction, si c'est un palindrome le stocker dans une variable chaîne de caractères
- si vous trouvez le prochain substrat palindrome et s'il est plus grand que le courant, remplacez-le par le courant.
- enfin votre variable string aura le réponse
Questions: 1. Cette algo fonctionne dans le temps O (N^2).
Algo 2:
- d'Inverser la chaîne et de le stocker dans diferent tableau
- trouver maintenant le plus grand substrat correspondant entre les deux le tableau
- mais cela aussi fonctionne dans le temps O(N^2)
pouvez-vous penser à une algo qui court dans un meilleur temps. Si possible O (n) temps
20 réponses
vous pouvez trouver le plus long palindrome en utilisant algorithme de Manacher dans O(n) time! Sa mise en œuvre se trouve ici et ici .
pour input String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE" il trouve la sortie correcte qui est 1234567887654321 .
L'Algo 2 peut ne pas fonctionner pour toutes les ficelles. Voici un exemple d'une telle chaîne de caractères "ABCDEFCBA".
non pas que la chaîne ait" ABC "et" CBA " comme substrat. Si vous inversez la chaîne originale, ce sera "ABCFEDCBA". et le plus long substrat correspondant est "ABC" qui n'est pas un palindrome.
vous pouvez avoir besoin de vérifier en plus si ce plus long substrat assorti est en fait un palindrome qui a la durée de fonctionnement de O(N^3).
autant que j'ai compris le problème, nous pouvons trouver des palindromes autour d'un index central et étendre notre recherche dans les deux sens, à droite et à gauche du centre. Étant donné que et sachant qu'il n'y a pas de palindrome sur les coins de l'entrée, nous pouvons définir les limites à 1 et longueur-1. Tout en faisant attention aux limites minimum et maximum de la chaîne, nous vérifions si les caractères aux positions des index symétriques (à droite et à gauche) sont les mêmes pour chaque position centrale jusqu'à ce que nous Atteignez notre limite supérieure.
la boucle extérieure est O (N) (N-2 itérations max), et la boucle intérieure est O (n) (autour de max (n / 2) - 1 itérations)
Voici mon implémentation Java en utilisant l'exemple fourni par d'autres utilisateurs.
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);
}
}
la sortie est la suivante:
marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321
avec regex et ruby vous pouvez scanner des palindromes courts comme ceci:
PROMPT> irb
>> s = "longtextwithranynarpalindrome"
=> "longtextwithranynarpalindrome"
>> s =~ /((\w)(\w)(\w)(\w)(\w))/; p
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w)\w)/; p
nil
=> nil
>> s =~ /((\w)(\w)(\w)(\w))/; p
nil
=> nil
>> s =~ /((\w)(\w)(\w)\w)/; p
"ranynar"
=> nil
on m'a posé cette question récemment. Voici la solution que j'ai finalement trouvée. Je l'ai fait en JavaScript parce que c'est assez simple dans ce langage.
le concept de base est que vous marchez la corde à la recherche du plus petit palindrome multi-caractères possible (soit un deux ou trois caractères un). Une fois que vous avez cela, élargir les frontières des deux côtés jusqu'à ce qu'il cesse d'être un palindrome. Si cette durée est plus longue que la plus longue, de le stocker et déplacer le long.
// 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;
}
cela pourrait certainement être nettoyé et optimisé un peu plus, mais il devrait avoir une assez bonne performance dans tous les cas sauf le pire (une chaîne de la même lettre).
Salut Voici mon code pour trouver le plus long palindrome dans la chaîne. Veuillez vous référer au lien suivant pour comprendre l'algorithme http://stevekrenzel.com/articles/longest-palnidrome
Test data used is 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;
}
voir article de Wikipedia sur ce sujet. Exemple algorithme de Manacher implémentation Java pour solution linéaire O (n) de l'article ci-dessous:
importer java.util.Tableaux; classe publique 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; } }
une solution efficace Regexp qui évite la force brute
commence avec la longueur de chaîne entière et fonctionne vers le bas à 2 caractères, existe dès qu'une correspondance est faite
pour "abaccddccefe" le regexp teste 7 matches avant de retourner 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
fonction
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
j'ai écrit le programme Java suivant par curiosité, simple et explicite HTH. Grâce.
/**
*
* @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);
}
}
Try the string - " HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE"; Ça devrait marcher pour les copains pairs et impairs. Merci beaucoup à Mohit!
utilisant 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;
}
le code suivant calcule Palidrom pour les chaînes de longueur Pair et Impair.
pas la meilleure solution mais fonctionne pour les deux cas
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;
}
- modifier chaîne de caractères pour séparer chaque caractère en utilisant un séparateur[ceci est pour incorporer des palindromes impairs et pairs]
- trouver des palindromes autour de chaque caractère le traitant comme un centre
nous pouvons trouver tous les palindromes de toute longueur en utilisant ceci.
Exemple :
mot = abcdcbc
modifiedString = A#b#c#d#C # B # C
palinCount = 1010105010301
longueur du plus long palindrome = 5;
palindrome le plus long = 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;
}
}
}
ceci retournera la plus longue chaîne palindrome de la chaîne donnée
-(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"];
}
= = sortie = = =
entrée: sortie abcccde: ccc
Entrée: abcccbd de Sortie: bcccb
entrée: sortie abedccde: sortie edcde
Entrée: abcccdeed de Sortie: acte
Entrée: abcccbadeed de Sortie: abcccba
Voici une implémentation en 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');pour la solution linéaire, vous pouvez utiliser L'algorithme de Manacher. Il y a un autre algorithme appelé algorithme de Gusfield, et ci-dessous est le code en 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();
}
}
vous pouvez trouver plus sur d'autres solutions telles que la meilleure solution O(N^2) ou l'algorithme de Manacher de mon propre blog .
ici, j'ai écrit une logique essayer:)
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"));
}
}
cette Solution est d'une complexité O(N^2). O (1) est la complexité de l'espace.
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 ;
}
}
Voici mon algorithme:
1) place le centre actuel à la première lettre
2) étendre simultanément à gauche et à droite jusqu'à ce que vous trouviez le palindrome maximum autour du centre actuel
3) si le palindrome que vous trouvez est plus grand que le palindrome précédent, mettez-le à jour
4) définit le centre actuel comme étant la lettre suivante
5) répétez l'étape 2) à 4) pour toutes les lettres dans la chaîne
Cela s'exécute en O(n).
J'espère que ça aidera.
le meilleur algorithme que j'ai jamais trouvé, avec la complexité 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;
}
}
ma solution est:
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;
}