微软面世试题-最大公共串-求两个字符串的最大公共子串的一个有意思的题目

bandaotidejia

UID: 40276
帖子: 160
积分: 368
在线时间: 1 天 11 小时

21^# bandaotidejia 发表于 2008-12-26 13:53

微软还用perl？

面试面世

iakuf

UID: 45144
帖子: 114
积分: 262
在线时间: 18 小时

22^# iakuf 发表于 2008-12-26 21:21

人家当时的要求是，无论你用什么方法来写

mfzz1134

UID: 33491
帖子: 70
积分: 161
在线时间: 7 小时

23^# mfzz1134 发表于 2008-12-27 01:13

经典DP,开矩阵是对地,效率最高.

wxlfh

UID: 22014
帖子: 1
积分: 2
在线时间: 10 分钟

24^# wxlfh 发表于 2008-12-28 10:30

Perl中可能效率不是最高也说不定。

cheveu

UID: 25977
帖子: 1
积分: 2
在线时间: 10 分钟

25^# cheveu 发表于 2009-01-02 13:36

我是外行，不会编程。
不过，不知道“卷积”可行不？

junonly

UID: 45927
帖子: 21
积分: 48
在线时间: 10 分钟

26^# junonly 发表于 2009-01-05 22:48

perl 新手, 写个试试

[Copy to clipboard] [ - ]

CODE:

#!/usr/bin/perl

&max_index_of_two_string('xabcdxxxveafa', 'eabcafeveafaeagagade');

sub max_index_of_two_string()
{
my ($str1, $str2) = @_;
my $max_index_of_two_string = undef;
if (length($str1) < length($str2)) {
      my $str = $str1;
      $str1 = $str2;
      $str2 = $str;
}
my $mark = 2;
while (length($str2) > 0) {
      while ($mark <= length($str2)) {
         my $pattern = substr($str2, 0, $mark);
         if ($str1 =~ /$pattern/) {
            if (length($pattern) > length($max_index_of_two_string)) {
                  $max_index_of_two_string = $pattern;
            }
         }
         $mark++;
      }
      if ($str2 =~ /(.)(.*)/) {
         $str2 = $2;
         $mark = 2;
      }
}
print $max_index_of_two_string;
}

machine

UID: 43012
帖子: 185
积分: 425
在线时间: 1 天 22 小时

27^# machine 发表于 2009-01-06 10:36

my $str = $str1;
$str1 = $str2;
$str2 = $str;
标准c语言写法。
perl 写法：
($str1,$str2)=($str2,$str1);

junonly

UID: 45927
帖子: 21
积分: 48
在线时间: 10 分钟

28^# junonly 发表于 2009-01-06 12:06

QUOTE:

原帖由 machine 于 2009-1-6 10:36 发表
my $str = $str1;
$str1 = $str2;
$str2 = $str;
标准c语言写法。
perl 写法：
($str1,$str2)=($str2,$str1);

这样就可以swap了，又学到新东西啊。