PHP - LCS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

<?php
/**
 * 生成 LCS 迭代路径图和打印路径图
 * @param string $str1 字符串1
 * @param string $str2 字符串2
 * @param array  $map  迭代路径图
 * @param array  $path 打印路径图
 */
function lcs_map(string $str1, string $str2, array &$map, array &$path) {
  for ($i = 0; $i <= strlen($str1); $i++) {
    for ($j = 0; $j <= strlen($str2); $j++) {
      $path[$i][$j] = 0; // 初始化 path
      if (0 == $i || 0 == $j) {
        // map 初始行和初始列均为 0
        $map[$i][$j] = 0;
      } else if ($str1[$i - 1] == $str2[$j - 1]) {
        // 字符相同, 则左上角+1
        $map[$i][$j] = $path[$i][$j] = $map[$i - 1][$j - 1] + 1;
      } else {
        // 字符不相同, 则选择上和左中最大值
        $map[$i][$j] = ($map[$i - 1][$j] > $map[$i][$j - 1]) ?
                        $map[$i - 1][$j] : $map[$i][$j - 1];
      }
    }
  }
}

/**
 * 返回最长公共子序列
 * @param string $str1 字符串1
 * @param string $str2 字符串2
 * @param array  $path 打印路径
 * @param int    $max  最长路径长度
 * @return string 子序列字符串
 */
function LCS(string $str1, string $str2, array $path, int $max) {
  $str = []; // 存储字符串

  $j = strlen($str2); // 初始化 $j

  for ($i = strlen($str1); $i > 0; $i--) {
    // 每当匹配到一个字符以后, 下一个字符必然在该列之前, 而非该列之后
    // 因此这里不需要每次循环都初始化 $j
    for (; $j > 0; $j--) {
      if ($path[$i][$j] == $max) {
        // 因为是从后往前遍历, 所以需要前端插入
        array_unshift($str, $str1[$i - 1]);
        $max--; // 路径长度 - 1
        break; // 改行已找到匹配字符, 跳过该行
      }
    }

    if (0 == $max) break; // 路径长度为 0, 退出循环

    // 这里会出现一个问题
    // 如果一行都没有匹配项, 那么 $j 就会循环至 0, 无法参与下一行匹配
    // 因此这里做一个判断, 如果路径长度 > 0 的时候 $j 已经减小到 0
    // 那么就初始化 $j
    if (0 == $j && $max > 0) $j = strlen($str2);
  }

  return implode('', $str); // 将字符数组拼接成字符串返回
}

$str1 = 'advantage';

$str2 = 'didactical';

if ($argc > 1) {
  $str1 = $argv[1];
  $str2 = $argv[2];
}

$map  = []; // 存储 LCS 迭代路径
$path = []; // 存储打印路径

lcs_map($str1, $str2, $map, $path);

echo "\nLCS 迭代路径图 MAP: \n";

for ($i = 0; $i <= strlen($str1); $i++) {
  for ($j = 0; $j <= strlen($str2); $j++) {
    echo $map[$i][$j] . "\t";
  }
  echo "\n";
}

echo "\nLCS 打印路径图 Path: \n";

for ($i = 0; $i <= strlen($str1); $i++) {
  for ($j = 0; $j <= strlen($str2); $j++) {
    echo $path[$i][$j] . "\t";
  }
  echo "\n";
}

echo "\n最长公共子序列: " .
     LCS($str1, $str2, $path, $map[strlen($str1)][strlen($str2)]) .
     "\n\n";