6

回文の文字列が与えられた場合、あと 1 文字を削除することで非回文に変換できる方法は何通りありますか?

たとえば、文字列が「b99b」の場合。次に、6つの方法でそれを行うことができます。

i) 1 文字目を削除 : "99b"
ii) 1 文字目、2 文字目を削除 : "9b"
iii) 1 文字目、3 文字目を削除 : "9b"
iv) 2 文字目、4 文字目を削除 : "b9"
v) 3 文字目、4 文字目を削除 : "b9"
vi) 4 番目の文字を削除: "b99"

これにアプローチする方法は？

PS: インデックス i の文字が 1 つの方法で削除され、別の方法では削除されないような i が存在する場合、2 つの方法は異なると見なされます。

4

5 に答える 5

6

文字列の回文サブシーケンスの数をカウントするための動的プログラミング アルゴリズムがあります。これを使用して、サブシーケンスの数 (単純に 2 n )から回文サブシーケンスの数を引くことにより、非パリンドローム サブシーケンスの数をカウントできます。O(n2)

このアルゴリズムは、OP の基準によってサブシーケンスをカウントします。結果のサブシーケンスが同じ要素を持っていても、要素を選択するために使用されるインデックスのリストに違いがある場合、2 つのサブシーケンスは異なると見なされます。

回文サブシーケンスをカウントするには、シーケンスの間隔に基づいてカウントを構築します。具体的には、次のように定義します。

Si,j= index でS始まり indexiで終わる部分文字列j(包括的)

Pi,j= のパリンドローム部分配列の数Si,j

ここで、すべての 1 要素区間は回文なので、次のようになります。

Pi,i = 1すべてのためにi < n

部分文字列が同じ要素 (つまり ) で開始および終了しない場合、回文部分列は次の要素で構成されます。Si ≠ Sj

  • 含むが含まないものSiSj

  • 含むが含まないものSjSi

  • どちらも含まないものSiSj

ここで、サブシーケンスの最初と 3 番目のセットの両方が含まれていることに注意してください。一方、2 番目と 3 番目のセットの両方が含まれています。まさに3セット目。その結果：Pi,j-1Pi+1,jPi+1,j-1

Pi,j = Pi+1,j + Pi,j-1 − Pi+1,j-1もしもSi ≠ Sj

しかし、もし? その場合、開始文字と終了文字だけからなる回文部分列だけでなく、 の後に からの部分列回文が続く回文を追加する必要があります。(技術的には、空のシーケンスは回文ですが、ここでは数えません。) 追加するサブシーケンスの数は P i+1,j-1 + 1 であり、上記の式で減算された double カウントを相殺します。そう：Si = SjSiSi+1,j-1Sj

Pi,j = Pi+1,j + Pi,j-1 + 1もし。Si = Sj

スペースを節約するために、実際に の増加する値を計算できます。最終結果 P 0,|S|-1を生成するには、これらのベクトルのうち 2 つを保持するだけで済みます。Pi,i+k for 0 ≤ i < |S|-kk

編集：

これは小さな python プログラムです。最初のものは上記のように回文サブシーケンスの数を計算し、ドライバーは非回文サブシーケンスの数を計算します (つまり、0 個以上の要素を削除して非回文を生成する方法の数; 元のシーケンスが回文である場合)。の場合、1 つまたは複数の要素を削除する方法の数です。)

# Count the palindromic subsequences of s
def pcount(s):
  length = len(s)
  p0 = [0] * (length + 1)
  p1 = [1] * length
  for l in range(1, length):
    for i in range(length - l):
      p0[i] = p1[i]
      if s[i] == s[i + l]:
        p1[i] += p1[i+1] + 1
      else:
        p1[i] += p1[i+1] - p0[i+1]
  # The "+ 1" is to account for the empty sequence, which is a palindrome.
  return p1[0] + 1

# Count the non-palindromic subsequences of s
def npcount(s):
  return 2**len(s) - pcount(s)
于 2013-02-17T18:07:57.347 に答える
2

これは完全な答えではなく、単なる提案です。

1 つまたは複数の文字を削除して、文字列を回文にしておく方法を数えてみます。次に、文字列を変更できる方法の総数からそれを引きます。

回文を変更して回文のままにしておく最も明白な方法は、文字i'thと(n-i)'th文字 (n は文字列の長さ) を削除することです。それを行う方法があり2^(n/2)ます。

"aaaa"このアプローチの問題は、対称的な変更のみが文字列を回文に保つことができると想定していることです。どのような変更でも回文になる場合などのケースを処理する方法を見つける必要があります。

于 2013-02-17T12:43:27.910 に答える
1

メモ化によるブルート フォースは非常に簡単です。

numWays(str): return 0 if str is empty
              return memo[str] if it exists
              memo[str] = numWays(str - firstChar) +
                          numWays(str - secondChar) +
                          ... +
                          1 if str is not a palindrome
              return memo[str]

基本的に、すべての文字を順番に削除し、結果の文字列の答えを保存します。文字列に含まれる同一の文字が多いほど、これは高速になります。

より効率的に行う方法がわからないので、理解できたら更新します。

于 2013-02-17T14:34:01.390 に答える
1

N 個の要素を持つ文字列の場合、2^N 個の可能な部分文字列 (文字列全体と空の部分文字列を含む) があります。したがって、すべての部分文字列を、省略された (または存在する) 文字のビット位置に「1」ビットを持ち、それ以外の場合は「0」ビットを持つ数値でエンコードできます。(文字列の長さが int のビット数 (ここでは size_t) よりも小さいと仮定すると、そうでない場合はビット文字列の別の表現が必要になります):

#include <stdio.h>
#include <string.h>

char string[] = "AbbA";
int is_palindrome (char *str, size_t len, size_t mask);

int main(void)
{
size_t len,mask, count;

len = strlen(string);

count =0;
for (mask = 1; mask < (1ul <<len) -1; mask++) {
        if ( is_palindrome (string, len, mask)) continue;
        count++;
        }

fprintf(stderr, "Len:=%u, Count=%u \n"
        , (unsigned) len , (unsigned) count );

return 0;
}

int is_palindrome (char *str, size_t len, size_t mask)
{
size_t l,r,pop;

for (pop=l=0, r = len -1; l < r; ) {
        if ( mask & (1u <<l)) { l++; continue; }
        if ( mask & (1u <<r)) { r--; continue; }
        if ( str[l] == str[r] ) return 1;
        l++,r--; pop++;
        }
return (pop <1) ? 1: 0;
}
于 2013-02-17T15:32:41.800 に答える
0

Haskellのバージョンは次のとおりです。

import Data.List

listNonPalindromes string = 
  filter (isNotPalindrome) (subsequences string)
    where isNotPalindrome str
            | fst substr == snd substr  = False
            | otherwise                 = True
           where substr = let a = splitAt (div (length str) 2) str
                          in (reverse (fst a), if even (length str) 
                                                  then snd a 
                                                  else drop 1 (snd a))

howManyNonPalindromes string = length $ listNonPalindromes string

*メイン>listNonPalindromes"b99b"
["b9"、 "b9"、 "b99"、 "9b"、 "9b"、"99b"]
*メイン>howManyNonPalindromes"b99b"
6

于 2013-02-17T16:50:49.627 に答える