태그 보관물: palindrome

palindrome

부분 문자열을 포함하는 회문까지의 최소 해밍 거리 영감을 얻었습니다 . 직무 비어

이것은 이제 제거 된 CS.SE 질문 에서 영감을 얻었습니다 .

직무

비어 있지 않은 두 입력 문자열 A와 B가 주어지면 A에서 B를 하위 문자열로 포함하는 회문까지의 최소 거리를 출력하십시오. 거리는 문자 교체 횟수 ( 해밍 거리 ) 로 정의됩니다 .

제한 사항

  • 현명한 입력 : 회문이 존재합니다. 이것은 | A | ≥ | B |.
  • A와 B에는 소문자 ASCII 문자 만 포함되며 소문자와 대문자는 구별됩니다 (다른 모든 문자와 마찬가지로).
  • 언어에서 ASCII 문자를 처리 할 수없는 경우 정수 (또는 다른 합리적인 데이터 유형)도 사용할 수 있으며 범위를 128 개 요소로 제한 할 수 있습니다.
  • stdin, 함수 인수, 명령 행 인수 등으로부터 입력을받을 수 있습니다.
  • stdout, 반환 값 등에 결과를 줄 수 있습니다.
  • 당신은 일하는 회문을 줄 필요가 없으며, 가장 작은 거리가 충분합니다.

예

A                   B            Output
thilloaoyreot       hello        4 (thelloaolleht)
benjonson           stack        9 (stackcats)
neversaynever!      odd          9 (neveroddoreven)
ppcggcpp            gg           0 (ppcggcpp)
stars               tat          1 (stats)

채점

이것은 코드 골프이며 바이트 단위로 가장 짧은 코드입니다.

답변

Pyth, 19 바이트

hSmsnVQd/#z_I#^+Qzl

데모

극단적 인 무차별 접근. 문자열 중 하나의 문자를 사용하여 적절한 길이의 모든 문자열을 생성하고 회문을 필터링하고 두 번째 입력을 포함하여 첫 번째 문자열에서 해밍 거리에 매핑하고 출력을 최소화하십시오.

설명:

hSmsnVQd/#z_I#^+Qzl
hSmsnVQd/#z_I#^+QzlQ     Variable introduction
                         Q = string A, z = string B.
               +Qz       Concatenate A and B
              ^   lQ     Form every string of length equal to len(A)using
                         characters from the concatenation.
             #           Filter on
           _I            Invariance under reversal (palindrome)
         #               Filter on
        / z              Nonzero occurences of B
  m                      Map to
    nV                   !=, vectorized over
      Qd                 A and the map input
   s                     Sum (gives the hamming weight)
hS                       Min

답변

Pyth, 45 바이트

hSmsnVQdf}zTsmm+hc2KsXcd+Bklz1z_hc2PKh-lQlz_B

온라인으로 사용해보십시오. 테스트 스위트.

나는 이것이 어떻게 밝혀 졌는지 여전히 정확하게 만족하지 않습니다. 그러나 적어도 지금 설명 없이는 이해하기가 어렵습니다. (성공합니다.)

설명

  • A의로 가지고 Q로와 B를 z.
  • m… _BQA와 그 반대의 경우 다음과 같이 계산하십시오 d.
    • m… 0에서 포함까지 h-ldlz모두 다음을 계산하십시오 .

      klen(A) - len(B)

      • +Bklz쌍을 얻으십시오 k, k + len(B).
      • cd분할 d하는 인덱스에서.
      • X… 1z두 번째 (중간) 부품을 B로 교체하십시오.
      • Ks조각을 연결하고에 저장하십시오 K. B는 이제 kA 또는 그 반대 위치 에 삽입됩니다 .
      • hc2결과 문자열을 두 개로 나누고 첫 번째 조각을 유지하십시오. 이것은 가능한 중간 문자로 문자열의 절반을 제공합니다.
      • hc2PK마지막 문자를 제거하고 첫 번째 조각을 유지하면서 동일한 분할을 수행하십시오. 이것은 가능한 중간 문자없이 문자열의 절반을 제공합니다.
      • +… _짧은 조각의 반대쪽을 더 긴 조각에 추가하십시오. 우리는 이제 회문이 있습니다.
  • s A와 그 결과를 연결합니다.
  • f}zT B를 포함하지 않는 모든 문자열을 제거하십시오.
  • m모든 결과 문자열에 대해 다음을 계산하십시오 d.
    • nVQd A와 쌍별 불평등을 가져옵니다. 이는 변경해야하는 쌍에 True를 제공합니다.
    • s목록을 요약하십시오. 이것은 해밍 거리를 제공합니다.
  • hS 최소한의 결과를 얻으십시오.

답변

자바 스크립트 (파이어 폭스 30+) 152 146 바이트

(A,B)=>Math.min(...[...Array(A[l='length']-B[l]+1)].map((_,i)=>[for(c of q=A.slice(j=t=0,i)+B+A.slice(i+B[l]))t+=(c!=A[j])+(c!=q[q[l]-++j])/2]|t))

무차별 접근 : A와 B의 각각의 가능한 중첩을 생성하고, 각각을 회문으로 만들고, A에서 해밍 거리를 계산하고, 결과 거리를 최소로 가져갑니다.

아마 조금 더 골프를 칠 수 있습니다 …

테스트 스 니펫

코드 스 니펫 표시

답변