标签: palindrome

_{这个问题是在PCRE模式中使用前瞻,嵌套引用和条件来匹配所有回文的教育演示,包括PCRE手册页中给出的递归模式无法匹配的回文.}

在PHP代码段中检查此PCRE模式:

$palindrome = '/(?x)
^
  (?:
      (.) (?=
              .*
              (
                \1
                (?(2) \2 | )
              )
              $
          )
  )*
  .?
  \2?
$


/';

这种模式似乎可以检测到回文,如本测试案例所示(另见ideone.com):

$tests = array(
  # palindromes
  '',
  'a',
  'aa',
  'aaa',
  'aba',
  'aaaa',
  'abba',
  'aaaaa',
  'abcba',
  'ababa',

  # non-palindromes
  'aab',
  'abab',
  'xyz',
);

foreach ($tests as $test) {
  echo sprintf("%s '%s'\n", preg_match($palindrome, $test), $test);  
}

那么这种模式如何运作？

笔记

此模式使用嵌套引用,这是此Java正则表达式如何检测回文中使用的类似技术？,但与Java模式不同,没有外观(但确实使用了条件).

另请注意,PCRE 手册页提供了一个递归模式以匹配一些回文:

# the recursive pattern to detect …

如果输入是'ABBA',那么可能回文是a,b,B,A,BB,ABBA.
我知道确定弦是否是回文很容易.这将是:

public static boolean isPalindrome(String str) {
 int len = str.length();
 for(int i=0; i<len/2; i++) {
     if(str.charAt(i)!=str.charAt(len-i-1) {
         return false;
     }
 return true;  
}

但找到回文子串的有效方法是什么？

我有一个字符串作为输入,必须打破两个子串中的字符串.如果左子串等于右子串,则执行一些逻辑.

我怎样才能做到这一点？

样品:

public bool getStatus(string myString)
{

}

示例:myString = "ankYkna",所以如果我们将它分成两个子串,它将是: left-part = "ank", right-part = "ank"(反转后).

我对Jon Limjap的采访事故感到好奇,并开始寻找有效的方法进行回文检测.我检查了回文高尔夫答案,在我看来答案中只有两个算法,反转字符串并检查尾部和头部.

def palindrome_short(s):
    length = len(s)
    for i in xrange(0,length/2):
        if s[i] != s[(length-1)-i]: return False
    return True

def palindrome_reverse(s):
    return s == s[::-1]

我认为这些方法都不能用于检测巨大DNA序列中的确切回文.我环顾四周,没有找到任何关于这种超高效方式的免费文章.

一种好的方法可能是以分而治之的方式并行化第一个版本,为每个线程或处理器分配一对char数组1..n和length-1-n..length-1.

什么是更好的方式？

你知道任何？

这是一个非常有趣的采访问题:

给出一个单词,将最少数量的字母附加到它上面以将其转换为回文结构.

例如,如果"hello"是给定的字符串,则结果应为"hellolleh".如果给出"coco",结果应该是"cococ".

我能想到的一种方法是将字符串的反向追加到原始字符串的末尾,然后尝试从末尾消除额外的字符.但是,我无法弄清楚如何有效地做到这一点.有没有人有任何想法？

首先是问题所在:

如果正整数在从左到右和从右到左读取时在十进制系统中的表示相同,则称为回文.对于给定的正整数K不超过1000000个数字,写入大于K的最小回文值输出.始终显示数字而不带前导零.

输入:第一行包含整数t,测试用例数.整数K在下一个t行中给出.

输出:对于每个K,输出大于K的最小回文.示例

输入:

2

808

2133

输出:

818

2222

其次这是我的代码:

// I know it is bad practice to not cater for erroneous input,
// however for the purpose of the execise it is omitted
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.lang.Exception;
import java.math.BigInteger;

public class Main
{    
    public static void main(String [] args){   
        try{
            Main instance = new Main(); // create an instance to access non-static
                                        // variables

            // Use java.util.Scanner to scan the get the input …

我知道使用自下而上动态编程方法的解决方案在O(n ^ 2)中解决了这个问题.我特意寻找自上而下的dp方法.是否有可能使用递归解决方案实现最长的回文子串？

这是我尝试过的但是在某些情况下它失败了,但我觉得我差不多正常.

#include <iostream>
#include <string>

using namespace std;

string S;
int dp[55][55];

int solve(int x,int y,int val)
{

    if(x>y)return val;
    int &ret = dp[x][y];
    if(ret!=0){ret = val + ret;return ret;}
    //cout<<"x: "<<x<<" y: "<<y<<" val: "<<val<<endl;
    if(S[x] == S[y])
        ret = solve(x+1,y-1,val+2 - (x==y));
    else
        ret = max(solve(x+1,y,0),solve(x,y-1,0));
    return ret;
}


int main()
{
    cin >> S;
    memset(dp,0,sizeof(dp));
    int num = solve(0,S.size()-1,0);
    cout<<num<<endl;
}

我试图解决Cormem的算法导论第3版(第405页)中的动态编程问题,该问题如下:

回文是一些字母表上的非空字符串,它向前和向后读取相同的字符串.回文的实例是长度为1的所有字符串,civic,racecar,和aibohphobia (回文的恐惧).

给出一个有效的算法来找到作为给定输入字符串的子序列的最长回文.例如,给定输入 character,您的算法应该返回carac.

好吧,我可以通过两种方式解决它:

第一解决方案

字符串的最长回文子序列(LPS)只是其自身及其反向的最长公共子序列.(我在解决了另一个要求序列的最长增加子序列的相关问题后构建了这个解决方案).由于它只是一个LCS变体,它还需要O(n²)时间和O(n²)存储器.

二解决方案:

第二个解决方案稍微详细一点,但也遵循一般的LCS模板.它来自以下重现:

lps(s[i..j]) = 
    s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
    max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise

用于计算lps长度的伪代码如下:

compute-lps(s, n):

    // palindromes with length 1
    for i = 1 to n:
        c[i, i] = 1
    // palindromes with length up to 2
    for i = 1 to n-1:
        c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1

    // …

为了找到将给定字符串转换为回文所需的最小插入次数,我找到了字符串(lcs_string)及其反向的最长公共子序列.因此,要进行的插入次数是length(s) - length(lcs_string)

知道要插入的数量,应该采用什么方法来找到等效的回文串？

例如 :

1)azbzczdzez

所需插入次数:5 Palindrome字符串:azbzcezdzeczbza

虽然同一根弦可能存在多个回文弦但我只想找到一个回文？

我编写了以下函数来查找字符串中最长的回文.它工作正常,但它不适用于像"中午"或"更红"的单词.我摆弄并改变了for循环中的第一行:

var oddPal = centeredPalindrome(i, i);

至

var oddPal = centeredPalindrome(i-1, i);

现在它有效,但我不明白为什么.我的直觉是,如果你正在检查一个奇怪的回文,它将在开始时有一个额外的字符(我把它白板化了,这就是我得出的结论).我的推理是否在正确的轨道上？

var longestPalindrome = function(string) {

  var length = string.length;
  var result = "";

  var centeredPalindrome = function(left, right) {
    while (left >= 0 && right < length && string[left] === string[right]) {
      //expand in each direction.
      left--;
      right++;
    }

    return string.slice(left + 1, right);
  }; 

  for (var i = 0; i < length - 1; i++) {
    var oddPal = centeredPalindrome(i, i); 
    var …