펄의 접미어 배열?

Question

이 질문은 밀접하게 관련이 있습니다 another stackoverflow question. 질문에 대한 매우 효율적인 해결책을 찾고 있습니다. 접미사 배열을 perl로 구현 했습니까?

여기 내 현재 펄 솔루션입니다.

chomp(my $ipstr = <>); 
my @bigstrchars = split(//, $ipstr); 
my $length = (length $ipstr); 
my $sum = 0; 
my $span = 1; 
my $flag = 0; 
while ($span < $length) { 
     for ($j=0; $j+$span<$length; $j++) { 
       if ($bigstrchars[$j] eq $bigstrchars[$j+$span]) { 
         $sum++; 
       } 
       else { 
         last; 
       } 
     } 
     if ($span == 1 && $sum == ($length-1)) { 
      $sum = $length * ($length+1) * 0.5; 
      $flag = 1; 
      last; 
     } 
     $span++; 
} 
unless ($flag) { 
    $sum += $length; 
} 

어떻게 개선 할 수 있습니까? 문제는 여기에 표명하는

편집

:

두 문자열 A와 B, 우리는 두 문자열에 공통 가장 긴 접두사의 길이로 문자열의 유사성을 정의합니다. 예를 들어 문자열 "abc"와 "abd"의 유사도는 2이고 문자열 "aaa"와 "aaab"의 유사도는 3입니다.

문제는 다음과 같은 유사성의 합을 계산하는 알고리즘을 제공하는 것입니다. 각각의 접미사가있는 문자열 S. 예를 들어, 문자열을 ababaa로 지정하십시오. 그런 다음 문자열의 접미사는 ababaa, babaa, abaa, baa, aa 및 a입니다. 이 문자열과 ababaa 문자열의 유사점은 각각 6,0,3,0,1,1입니다. 따라서 대답은 6 + 0 + 3 + 0 + 1 + 1 = 11

Answer 1

약 Array::Suffix 어떨까요?

Answer 2

알고리즘을 올바르게 이해하고 가장 긴 공통 접두어의 합계를 계산하려는 경우 오름차순 사전 식 정렬이 부족하므로 구현이 잘못되었습니다. @subipstrs

@subipstrs = (
    ['a'], 
    ['a', 'a'], 
    ['a', 'b', 'a', 'a'], 
    ['a', 'b', 'a', 'b', 'a', 'a'], 
    ['b', 'a', 'a'], 
    ['b', 'a', 'b', 'a', 'a'] 
); 

가 나타내는 접미사 배열

5 | a 
4 | aa 
2 | abaa 
0 | ababaa 
3 | baa 
1 | babaa 

를 생성합니다이 참조하는 문제의 예를 들어 문자열 ababaa를 들어

#!/usr/bin/perl 
use strict; 
use warnings; 

chomp(my $ipstr = <>);  
my @subipstrs = map [split//], sort map{substr $ipstr, $_} 0 .. length($ipstr) - 1; 
my $sum = 0; 

for my $i (1 .. $#subipstrs) { 
    my @last = @{$subipstrs[$i-1]}; 
    my @this = @{$subipstrs[$i]}; 
    my $j = 0; 
    $sum++ while $j < @last && $j < @this && $last[$j] eq $this[$j++]; 
} 

:

는 여기에 귀하의 문제를 해결하는 하나의 방법입니다

이렇게하면 lcp 쌍이 일치하는 동안 엘리먼트별로 이웃 배열 참조를 비교하고 총 일치 수를 더한다. 결과 7하지 (11)의 총

5 | a  | 0 
4 | aa  | 1 
2 | abaa | 1 
0 | ababaa | 3 
3 | baa | 0 
1 | babaa | 2 

이다.

편집 : 이것은 당신이 관심있는 문제 해결 :

#!/usr/bin/perl 
use strict; 
use warnings; 

chomp(my $ipstr = <>); 
my $len = my $sum = length($ipstr); 

for my $i (1 .. $len -1) { 
    my $substr = substr $ipstr, $i; 
    chop $substr while $substr ne substr $ipstr, 0, length($substr); 
    $sum += length($substr); 
} 

을 그리고 당신의 예를 들어 문자열과 1M 반복으로 조금 더 빠른 솔루션보다 :

trinity 80906/s  -- -32% 
flesk 119332/s  47%  -- 

EDIT2 : 문자열의 처음에서부터 작동하고 더 빨리 부정적인 일치를 버릴 수 있으므로이 방법이 더 빠릅니다.

#!/usr/bin/perl 
use strict; 
use warnings; 

chomp(my $ipstr = <>); 
my $len = my $sum = length($ipstr); 

for my $i (1 .. $len - 1) { 
    my $ipstrcopy = reverse $ipstr; 
    my $substr = reverse substr $ipstr, $i; 
    my ($slen, $j) = (length($substr), 0); 
    $sum++ while $j++ <= $slen && chop $ipstrcopy eq chop $substr; 
} 

ababaa 및 100K 반복 :

trinity 81967/s  -- -24% 
flesk 107527/s  31%  -- 

abcdefghijklmnopqrstuvwxyz 및 100K 반복 :

trinity 26178/s  -- -15% 
flesk 30769/s  18%  -- 

aaaaaaaaaaabbbaaaaaaaaaaaaaaaabbbaaaaaaaaa 및 100K 반복은 :

trinity 5435/s  -- -30% 
flesk 7800/s  44%  -- 

알고리즘은 아마 역전시킴으로써 더욱 향상시킬 수있다 루프 앞에 $ipstr을 입력하거나 chop 대신 substr을 사용하십시오.

Answer 3

플렉스의 솔루션은 꽤 우아합니다. 효율성을 요구 한 다음 개선을 요청했습니다. Perl에 관해서는 3 개월이 지난 후 가장 좋은 개선이 될 때 이해할 시간이 적어지는 것을 발견했습니다. 그래서 좀 더 기술적 인 고려 뭔가 고려 :

use Data::Dumper; 
use strict; 

    main(); 

    sub main { 
     my $string = "ababaa";       # input string 
     my $parts;          # hash ref 
     my @suffixes = split '',$string;    # break input into tokens 
     my $running_sum = 0; 
     $"=''; 

     # Build suffix tree 
     for (0..$#suffixes){ 
     $parts->{"@suffixes"}=0; 
     shift @suffixes; 
     } 


     # Compare suffixes to initial string 
     for my $suffix (sort keys %$parts){ 
      $parts->{$suffix} = getMatches($suffix,$string); 
      $running_sum  += $parts->{$suffix}; 
     } 

     # Output 
     $Data::Dumper::Sortkeys++; 
     print Dumper($parts), "\nTotal Matches: $running_sum"; 
    } 

    sub getMatches{ 
     my ($word,$string) = @_; 
     my $part = ''; 
     my $offset = 0; 
     my $matches = 0; 

     for (0..(length($word) - 1)){ 
     $offset++; 
     $part = substr($word,0,$offset); 
     if ($string =~ /^$part/){ $matches++; } 
     } 
     return $matches; 
    } 

이 개선 될 수 명백한 비 효율성 (루프, 정규식 비교, 서브 루틴 호출),하지만이 답변의 요점은 내가했습니다 뭔가 대안입니다 더 나은 미래 이해력의 유일한 이익을 위해 더 나은 것으로 이미 확인되었습니다.