Я нашел решение. У меня была такая же проблема, и ошибка, установив «amara».
C:\programs\mingw\
c:\programs\MinGW\bin;
в файл PATH C:\Python26\Lib\distutils\distutils.cfg
, чтобы быть: [build]
compiler=mingw32
easy_install.exe amara
. Убедитесь, что среда установлена, открыв новый cmd.exe
.
Следующий код вычисляет 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;
}
Для линейного решения вы можете использовать алгоритм Манахера. Существует еще один алгоритм, называемый алгоритмом Гусфилда, а ниже - код в 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) или алгоритм Манахера из мой собственный блог .
Вот реализация в 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');
Эффективное решение Regexp
, которое позволяет избежать грубой силы
Начинается со всей длины строки и работает вниз до двух символов, существует, как только будет выполнено совпадение
. Для "abaccddccefe"
regexp испытывает 7 совпадений перед возвратом 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)
blockquote>Dim strTest wscript.echo Palindrome("abaccddccefe")
Sub Test() Dim strTest MsgBox Palindrome("abaccddccefe") End Sub
function
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
Я написал следующую программу Java из любопытства, простой и понятной HTH. Спасибо.
/**
*
* @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 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"));
}
}
См. статью в Википедии по этой теме. Пример Алгоритм Manacher's Реализация Java для линейного решения O (n) из следующей статьи:
import java.util.Arrays; public class ManachersAlgorithm {public static String findLongestPalindrome (String s) {if (s == null || s.length () == 0) return "";
blockquote>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; } }
Вы можете найти самый длинный палиндром с помощью алгоритма Manacher's в O(n)
раз! Его реализацию можно найти здесь здесь и здесь .
Для входа String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"
он находит правильный вывод, который является 1234567887654321
.
Вот мой алгоритм:
1) установить текущий центр как первую букву
2) одновременно развернуть влево и вправо, пока не найдете максимальный палиндром вокруг текущий центр
3) если палиндром, который вы находите, больше, чем предыдущий палиндром, обновите его
4) установите текущий центр следующей буквой
5) повторите шаг 2) - 4) для всех букв в строке
Это выполняется в O (n).
Надеюсь, что это поможет.
Это возвращает длинную строку палиндрома из заданной строки
-(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"];
}
== OUTPUT ===
Вход: abcccde Выход: ccc
Вход: abcccbd Выход: bcccb
Вход: abedccde Выход: edccde
Вход: abcccdeed Выход: документ
Вход: abcccbadeed Выход: abcccba
Насколько я понял эту проблему, мы можем найти палиндромы вокруг центрального индекса и развернуть наш поиск в обоих направлениях, справа и слева от центра. Учитывая это и зная, что на углах ввода нет палиндрома, мы можем установить границы на 1 и длину-1. Обращая внимание на минимальную и максимальную границы String, мы проверяем, совпадают ли символы в положениях симметричных индексов (справа и слева) для каждого центрального положения, пока мы не достигнем нашего максимального верхнего граничного центра.
Внешний цикл равен O (n) (max n-2 итерации), а внутренний цикл while - O (n) (max вокруг (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
Привет Вот мой код, чтобы найти самый длинный палиндром в строке. Пожалуйста, обратитесь к следующей ссылке, чтобы понять алгоритм 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;
}
Мы можем найти все палиндромы всей длины, используя это.
Образец:
word = abcdcbc
modifiedString = a # b # c # d # c # b # c
palinCount = 1010105010301
длина самого длинного палиндрома = 5;
самый длинный палиндром = bcdcb
открытый класс 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;
}
}
}
Попробуйте строку - «HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE»; Он должен работать для четных и нечетных друзей. Огромное спасибо Мохиту!
с использованием пространства имен 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;
}
Лучший алгоритм, который я когда-либо нашел, со сложностью 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;
}
Это решение имеет сложность 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 ;
}
}
Algo 2 может не работать для всей строки. Вот пример такой строки «ABCDEFCBA».
Не то, что строка имеет «ABC» и «CBA» в качестве подстроки. Если вы измените исходную строку, это будет «ABCFEDCBA». и самая длинная совпадающая подстрока - это «ABC», которая не является палиндром.
Возможно, вам потребуется дополнительно проверить, является ли эта самая длинная совпадающая подстрока фактически палиндром, который имеет время работы O (n ^ 3).