pung96's perlog

my $common = 'ABC';

my @str;

$str[0] = 'AA BBCD ABC bbbc aaaa';

$str[1] = 'BBAA BBCD ABC bbb';

$str[2] = '123BBAA BBCD ABC bbFSKFSJLK';

$str[3] = '239I2P3IBBAA BBCD ABC bbb FLSKJFLSKJDFLJS';

$str[4] = 'ABC bbb';




@str의 문자열들에서 ABC를 포함하면서 공통되는 가장 큰 문자열 셋을 찾는 것.

이경우네는 ABC bbb 가 된다.



물론 효율을 따지면,, 한글자한글자 비교해야 겠지만

일단 효율 무시, 정규표현식을 써보자



두 문자열의 공통된 부분을 찾는 건 꽤 쉽다. 일단 두 문자열을 합친 다음에 다음처럼 만들면 된다.




($max_common) = (($str[0].$str[1]) =~ /^.*?(.*$common.*).*?\1.*?$/) 




자세한 설명은.. 생략

한가지만 얘기하자면 첫번째 ()에서 찾은것이 \1이 된다는 정도.

사실 경우에 따라 몇가지 버그를 가지고 있기는 하다

한 문자열에 ABC가 여러개 있다면 우리가 원하는 대로 나오지 않을 수 있다.

이경우에는 한 문자열에 ABC가 하나만 있다고 가정하자. (혹은 그렇게 만들 루틴을 가지고 있다고)



그럼 여러개의 문자열에 대해서는 어떻게 할까?

여러개의 문자열을 모두 합쳐서 찾으면 좋겠지만, 그럼 위와 같은 문제가 다시 발생한다.

어쩔수 없이 정규표현식을 문자열 개수만큼 돌려야 한다.




my $max_common = shift @str;

($max_common) = (($max_common.$_) =~ /^.*?(.*$common.*).*?\1.*?$/) for @str;

print $max_common;




우왕 굿.



그러나 효율에는 심각한 문제가 있다.

이 정규표현식의 경우는 backtracking을 이용해서 꽤 과도하게 검색을 하기 때문에 긴 문자열에는 적합하지 않다.



테스트로 17kbytes 문서 두개를 이용해서 비교해 봤는데 10분 동안 돌린후에 테스트를 포기했다.

문자열의 길이에 대해 어느정도 효율을 가지는지 테스트해보고 싶지만,, 귀차니즘으로 생량.



그것은 그대의 손에!!