GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Longest Palindromic Subsequence · Homie980/AlgorithmVisualizer@8b68ee2

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • algorithm
    • category.json
    • dp/longest_palindromic_subsequence
      • basic
        • code.js
        • data.js
      • desc.json
  • gulpfile.babel.js
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎algorithm/category.json‎

Copy file name to clipboardExpand all lines: algorithm/category.json
+3-2Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020
"knapsack_problem": "Knapsack Problem",
2121
"longest_common_subsequence": "Longest Common Subsequence",
2222
"longest_increasing_subsequence": "Longest Increasing Subsequence",
23+
"longest_palindromic_subsequence": "Longest Palindromic Subsequence",
2324
"max_subarray": "Maximum Subarray",
2425
"max_sum_path": "Maximum Sum Path",
2526
"pascal_triangle": "Pascal's Triangle",
@@ -57,8 +58,8 @@
5758
},
5859
"number_theory": {
5960
"list": {
60-
"euclidean_algorithm": "Euclidean Algorithm",
61-
"sieve_of_eratosthenes": "Sieve of Eratosthenes"
61+
"euclidean_algorithm": "Euclidean Algorithm",
62+
"sieve_of_eratosthenes": "Sieve of Eratosthenes"
6263
},
6364
"name": "Number Theory"
6465
},
Collapse file

‎algorithm/dp/longest_palindromic_subsequence/basic/code.js‎

Copy file name to clipboard
+60Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
function max(a,b) {
2+
if(a>b){
3+
return a;
4+
} else {
5+
return b;
6+
}
7+
}
8+
logger._print("LPS for any string with length = 1 is 1");
9+
for(i=2;i<=N;i++) {
10+
logger._print("--------------------------------------------------");
11+
logger._print("Considering a sub-string of length "+i);
12+
logger._print("--------------------------------------------------");
13+
for(j=0;j<N-i+1;j++) {
14+
var k = j+i-1;
15+
tracer._select(j)._wait();
16+
tracer._notify(k)._wait();
17+
18+
logger._print("Comparing "+seq[j] + " and "+seq[k]);
19+
20+
if(seq[j]==seq[k] && i==2) {
21+
logger._print("They are equal and size of the string in the interval"+j+" to "+k+" is 2, so the Longest Palindromic Subsequence in the Given range is 2");
22+
23+
matrix._notify(j,k)._wait();
24+
25+
L[j][k]=2;
26+
matrix._setData(L);
27+
28+
matrix._denotify(j,k)._wait();
29+
30+
} else if(seq[j]==seq[k]) {
31+
logger._print("They are equal, so the Longest Palindromic Subsequence in the Given range is 2 + the Longest Increasing Subsequence between the indices "+(j+1)+" to "+(k-1));
32+
33+
matrix._notify(j,k)._wait();
34+
matrix._select(j+1,k-1)._wait();
35+
36+
L[j][k] = L[j+1][k-1] + 2;
37+
matrix._setData(L);
38+
39+
matrix._denotify(j,k)._wait();
40+
matrix._deselect(j+1,k-1)._wait();
41+
42+
} else {
43+
logger._print("They are NOT equal, so the Longest Palindromic Subsequence in the Given range is the maximum Longest Increasing Subsequence between the indices "+(j+1)+" to "+(k) + " and "+(j)+" to "+(k-1));
44+
matrix._notify(j,k)._wait();
45+
matrix._select(j+1,k)._wait();
46+
matrix._select(j,k-1)._wait();
47+
48+
L[j][k] = max(L[j+1][k],L[j][k-1]);
49+
matrix._setData(L);
50+
51+
matrix._denotify(j,k)._wait();
52+
matrix._deselect(j+1,k)._wait();
53+
matrix._deselect(j,k-1)._wait();
54+
}
55+
logger._print("--------------------------------------------------");
56+
tracer._deselect(j)._wait();
57+
tracer._denotify(k)._wait();
58+
}
59+
}
60+
logger._print("Longest Increasing Subsequence of the given string = L[0]["+(N-1)+"]="+L[0][N-1]);
Collapse file

‎algorithm/dp/longest_palindromic_subsequence/basic/data.js‎

Copy file name to clipboard
+23Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
2+
var tracer = new Array1DTracer('Input Text');
3+
var matrix = new Array2DTracer('Matrix');
4+
var logger = new LogTracer();
5+
6+
7+
var seq = "BBABCBCAB";
8+
var N;
9+
N = seq.length;
10+
11+
12+
var L = new Array(N);
13+
14+
var i,j;
15+
for(i=0;i<N;i++) {
16+
L[i]= new Array(N);
17+
}
18+
for(i=0;i<N;i++) {
19+
L[i][i]=1;
20+
}
21+
22+
tracer._setData(seq);
23+
matrix._setData(L);
Collapse file

‎algorithm/dp/longest_palindromic_subsequence/desc.json‎

Copy file name to clipboard
+13Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Longest Palindromic Subsequence": "Find the length of the longest palindromic subsequence in a given sequence",
3+
"Complexity": {
4+
"time": "O(n<sup>2</sup>)",
5+
"space": "O(n<sup>2</sup>)"
6+
},
7+
"References": [
8+
"<a href='http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/'>GeeksForGeeks</a>"
9+
],
10+
"files": {
11+
"basic": "Longest Palindromic Subsequence"
12+
}
13+
}
Collapse file

‎gulpfile.babel.js‎

Copy file name to clipboardExpand all lines: gulpfile.babel.js
+1Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,4 @@
1+
var Promise = require ('es6-promise').Promise;
12
'use strict';
23

34
import path from "path";

0 commit comments

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.