Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- $trace = [];
- $str1 = 'bcadb';
- $N = strlen($str1);
- $str2 = 'acdb';
- $M = strlen($str2);
- $MAX = $N + $M;
- echo 'MAX=' . $MAX . PHP_EOL;
- $lengthOfSES = 0;
- $V[1] = 0;
- for ($D = 0; $D <= $MAX; $D++) {
- echo 'D=' . $D . PHP_EOL;
- for ($k = -$D; $k <= $D; $k += 2) {
- echo ' k=' . $k . PHP_EOL;
- if ($k == -$D || ($k != $D && $V[$k - 1] < $V[$k + 1])) {
- $x = $V[$k + 1];
- } else {
- $x = $V[$k - 1] + 1;
- }
- $y = $x - $k;
- while ($x < $N && $y < $M && ($str1[$x - 1 + 1] == $str2[$y - 1 + 1])) {
- $x++;
- $y++;
- }
- $V[$k] = $x;
- if ($x >= $N && $y >= $M) {
- $lengthOfSES = $D;
- print_r($V);
- echo '$lengthOfSES is ' . $D . PHP_EOL;
- die;
- }
- }
- }
- print('Length of an SES is greater than MAX');
- }
Add Comment
Please, Sign In to add comment