Posted on by Kalkicode
Code Dynamic Programming

# Longest palindromic substring using dynamic programming

Dynamic programming is a technique used to solve complex problems by breaking them down into smaller overlapping subproblems and solving them independently. In this article, we will explore how dynamic programming can be used to find the longest palindromic substring in a given string. A palindromic substring is a substring that remains the same when read forwards or backwards.

## Problem Statement

Given a string, we want to find the longest palindromic substring within that string. For example, in the string "nitiiiigi", the longest palindromic substring is "iiii", and in the string "vvvvivfvim", the longest palindromic substring is "ivfvi". Our task is to develop an algorithm using dynamic programming to efficiently solve this problem.

## Pseudocode Algorithm with Explanation

Let's walk through the algorithm step by step:

1. Start by defining the function findLPS which takes a string called text as input.
2. Get the length of the input text and store it in the variable n.
3. If the length of the text is zero, return as there are no palindromic substrings to find.
4. Initialize variables length, start, and dp[n][n].
5. Initialize all elements of dp to 0 using nested for loops.
6. Set the diagonal elements of dp to 1 because a single character is always a palindrome.
7. Compare adjacent characters in the text using another for loop.
8. If two adjacent characters are the same, set dp[i][i+1] to 1, update the length to 2, and store the starting index in the variable start.
9. Iterate over k from 3 to n (length of text + 1).
10. Within the loop, use nested loops to iterate over all possible substrings of length k.
11. Check if the substring from i to j (i + k - 1) is a palindrome by verifying if dp[i + 1][j - 1] is 1 and text[i] is equal to text[j].
12. If the substring is a palindrome, set dp[i][j] to 1 and update the length and start variables if necessary.
13. After finding the longest palindromic substring, display the given text.
14. Print the resultant palindrome by iterating over the characters from start to start + length - 1.
15. Print the length of the resultant palindrome.
16. End the function.
17. In the main function, call findLPS with different test cases to demonstrate the algorithm's functionality.

## Code Solution

/*
C program for
Longest palindromic substring using dynamic programming
*/
#include <stdio.h>
#include <string.h>

void findLPS(char *text)
{
// Get length of text
int n = strlen(text);
if (n == 0)
{
// When text is empty
return;
}
int length = 1;
int start = 0;
int dp[n][n];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
dp[i][j] = 0;
}
}
// Set diagonal elements value is 1
for (int i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
for (int i = 0; i < n - 1; ++i)
{
if (text[i] == text[i + 1])
{
// When adjacent elements is similar
dp[i][i + 1] = 1;
// Change resultant length
length = 2;
start = i;
}
}
for (int k = 3; k <= n; ++k)
{
for (int i = 0; i < n - k + 1; ++i)
{
int j = i + k - 1;
if (dp[i + 1][j - 1] && text[i] == text[j])
{
dp[i][j] = 1;
if (k > length)
{
// Change resultant length
length = k;
// Update resultant starting location
start = i;
}
}
}
}
// Display given text
printf("\n Given string : %s", text);
printf("\n Result : ");
// Display resultant palindrome
for (int i = start; i <= start + length - 1; ++i)
{
printf("%c", text[i]);
}
// Display length of resultant palindrome
printf("\n Resultant length : %d", length);
}
int main(int argc, char
const *argv[])
{
// Test
// iiii => 4
findLPS("nitiiiigi");
// ivfvi => 5
findLPS("vvvvivfvim");
// civic => 5
findLPS("xyzacivicxrs");
// opo => 3
findLPS("ttoopo");
return 0;
}

#### Output

Given string : nitiiiigi
Result : iiii
Resultant length : 4
Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5
Given string : xyzacivicxrs
Result : civic
Resultant length : 5
Given string : ttoopo
Result : opo
Resultant length : 3
// Java program for
// Longest palindromic substring using dynamic programming
public class LongestPalindrome
{
public void findLPS(String text)
{
// Get length of text
int n = text.length();
if (n == 0)
{
// When text is empty
return;
}
int length = 1;
int start = 0;
int[][] dp = new int[n][n];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
dp[i][j] = 0;
}
}
// Set diagonal elements value is 1
for (int i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
for (int i = 0; i < n - 1; ++i)
{
if (text.charAt(i) == text.charAt(i + 1))
{
// When adjacent elements is similar
dp[i][i + 1] = 1;
// Change resultant length
length = 2;
start = i;
}
}
for (int k = 3; k <= n; ++k)
{
for (int i = 0; i < n - k + 1; ++i)
{
int j = i + k - 1;
if (dp[i + 1][j - 1] != 0 && text.charAt(i) == text.charAt(j))
{
dp[i][j] = 1;
if (k > length)
{
// Change resultant length
length = k;
// Update resultant starting location
start = i;
}
}
}
}
// Display given text
System.out.print("\n Given string : " + text);
System.out.print("\n Result : ");
// Display resultant palindrome
for (int i = start; i <= start + length - 1; ++i)
{
System.out.print(text.charAt(i));
}
// Display length of resultant palindrome
System.out.print("\n Resultant length : " + length);
}
public static void main(String[] args)
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
}

#### Output

Given string : nitiiiigi
Result : iiii
Resultant length : 4
Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5
Given string : xyzacivicxrs
Result : civic
Resultant length : 5
Given string : ttoopo
Result : opo
Resultant length : 3
#include <iostream>
#include <string>
using namespace std;

// C++ program for
// Longest palindromic substring using dynamic programming

class LongestPalindrome
{
public: void findLPS(string text)
{
// Get length of text
int n = text.length();
if (n == 0)
{
// When text is empty
return;
}
int length = 1;
int start = 0;
int dp[n][n];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
dp[i][j] = 0;
}
}
// Set diagonal elements value is 1
for (int i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
for (int i = 0; i < n - 1; ++i)
{
if (text[i] == text[i + 1])
{
// When adjacent elements is similar
dp[i][i + 1] = 1;
// Change resultant length
length = 2;
start = i;
}
}
for (int k = 3; k <= n; ++k)
{
for (int i = 0; i < n - k + 1; ++i)
{
int j = i + k - 1;
if (dp[i + 1][j - 1] != 0 && text[i] == text[j])
{
dp[i][j] = 1;
if (k > length)
{
// Change resultant length
length = k;
// Update resultant starting location
start = i;
}
}
}
}
// Display given text
cout << "\n Given string : " << text;
cout << "\n Result : ";
// Display resultant palindrome
for (int i = start; i <= start + length - 1; ++i)
{
cout << text[i];
}
// Display length of resultant palindrome
cout << "\n Resultant length : " << length;
}
};
int main()
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
return 0;
}

#### Output

Given string : nitiiiigi
Result : iiii
Resultant length : 4
Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5
Given string : xyzacivicxrs
Result : civic
Resultant length : 5
Given string : ttoopo
Result : opo
Resultant length : 3
// Include namespace system
using System;
// Csharp program for
// Longest palindromic substring using dynamic programming
public class LongestPalindrome
{
public void findLPS(String text)
{
// Get length of text
int n = text.Length;
if (n == 0)
{
// When text is empty
return;
}
int length = 1;
int start = 0;
int[,] dp = new int[n,n];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
dp[i,j] = 0;
}
}
// Set diagonal elements value is 1
for (int i = 0; i < n; ++i)
{
dp[i,i] = 1;
}
for (int i = 0; i < n - 1; ++i)
{
if (text[i] == text[i + 1])
{
// When adjacent elements is similar
dp[i,i + 1] = 1;
// Change resultant length
length = 2;
start = i;
}
}
for (int k = 3; k <= n; ++k)
{
for (int i = 0; i < n - k + 1; ++i)
{
int j = i + k - 1;
if (dp[i + 1,j - 1] != 0 && text[i] == text[j])
{
dp[i,j] = 1;
if (k > length)
{
// Change resultant length
length = k;
// Update resultant starting location
start = i;
}
}
}
}
// Display given text
Console.Write("\n Given string : " + text);
Console.Write("\n Result : ");
// Display resultant palindrome
for (int i = start; i <= start + length - 1; ++i)
{
Console.Write(text[i]);
}
// Display length of resultant palindrome
Console.Write("\n Resultant length : " + length);
}
public static void Main(String[] args)
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
}

#### Output

Given string : nitiiiigi
Result : iiii
Resultant length : 4
Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5
Given string : xyzacivicxrs
Result : civic
Resultant length : 5
Given string : ttoopo
Result : opo
Resultant length : 3
package main
import "fmt"
// Go program for
// Longest palindromic substring using dynamic programming

func findLPS(text string) {
// Get length of text
var n int = len(text)
if n == 0 {
// When text is empty
return
}
var length int = 1
var start int = 0
var dp = make([][] int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int,n)
}
// Set diagonal elements value is 1
for i := 0 ; i < n ; i++ {
dp[i][i] = 1
}
for i := 0 ; i < n - 1 ; i++ {
if text[i] == text[i + 1] {
// When adjacent elements is similar
dp[i][i + 1] = 1
// Change resultant length
length = 2
start = i
}
}
for k := 3 ; k <= n ; k++ {
for i := 0 ; i < n - k + 1 ; i++ {
var j int = i + k - 1
if dp[i + 1][j - 1] != 0 && text[i] == text[j] {
dp[i][j] = 1
if k > length {
// Change resultant length
length = k
// Update resultant starting location
start = i
}
}
}
}
// Display given text
fmt.Print("\n Given string : ", text)
fmt.Print("\n Result : ")
// Display resultant palindrome
for i := start ; i <= start + length - 1 ; i++ {
fmt.Print(string(text[i]))
}
// Display length of resultant palindrome
fmt.Print("\n Resultant length : ", length)
}
func main() {

// Test
// iiii => 4
findLPS("nitiiiigi")
// ivfvi => 5
findLPS("vvvvivfvim")
// civic => 5
findLPS("xyzacivicxrs")
// opo => 3
findLPS("ttoopo")
}

#### Output

Given string : nitiiiigi
Result : iiii
Resultant length : 4
Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5
Given string : xyzacivicxrs
Result : civic
Resultant length : 5
Given string : ttoopo
Result : opo
Resultant length : 3
<?php
// Php program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
public  function findLPS(\$text)
{
// Get length of text
\$n = strlen(\$text);
if (\$n == 0)
{
// When text is empty
return;
}
\$length = 1;
\$start = 0;
\$dp = array_fill(0, \$n, array_fill(0, \$n, 0));
// Set diagonal elements value is 1
for (\$i = 0; \$i < \$n; ++\$i)
{
\$dp[\$i][\$i] = 1;
}
for (\$i = 0; \$i < \$n - 1; ++\$i)
{
if (\$text[\$i] == \$text[\$i + 1])
{
// When adjacent elements is similar
\$dp[\$i][\$i + 1] = 1;
// Change resultant length
\$length = 2;
\$start = \$i;
}
}
for (\$k = 3; \$k <= \$n; ++\$k)
{
for (\$i = 0; \$i < \$n - \$k + 1; ++\$i)
{
\$j = \$i + \$k - 1;
if (\$dp[\$i + 1][\$j - 1] != 0 && \$text[\$i] == \$text[\$j])
{
\$dp[\$i][\$j] = 1;
if (\$k > \$length)
{
// Change resultant length
\$length = \$k;
// Update resultant starting location
\$start = \$i;
}
}
}
}
// Display given text
echo("\n Given string : ".\$text);
echo("\n Result : ");
// Display resultant palindrome
for (\$i = \$start; \$i <= \$start + \$length - 1; ++\$i)
{
echo(\$text[\$i]);
}
// Display length of resultant palindrome
echo("\n Resultant length : ".\$length);
}
}

function main()
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
main();

#### Output

Given string : nitiiiigi
Result : iiii
Resultant length : 4
Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5
Given string : xyzacivicxrs
Result : civic
Resultant length : 5
Given string : ttoopo
Result : opo
Resultant length : 3
// Node JS program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
findLPS(text)
{
// Get length of text
var n = text.length;
if (n == 0)
{
// When text is empty
return;
}
var length = 1;
var start = 0;
var dp = Array(n).fill(0).map(() => new Array(n).fill(0));
// Set diagonal elements value is 1
for (var i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
for (var i = 0; i < n - 1; ++i)
{
if (text.charAt(i) == text.charAt(i + 1))
{
// When adjacent elements is similar
dp[i][i + 1] = 1;
// Change resultant length
length = 2;
start = i;
}
}
for (var k = 3; k <= n; ++k)
{
for (var i = 0; i < n - k + 1; ++i)
{
var j = i + k - 1;
if (dp[i + 1][j - 1] != 0 &&
text.charAt(i) == text.charAt(j))
{
dp[i][j] = 1;
if (k > length)
{
// Change resultant length
length = k;
// Update resultant starting location
start = i;
}
}
}
}
// Display given text
process.stdout.write("\n Given string : " + text);
process.stdout.write("\n Result : ");
// Display resultant palindrome
for (var i = start; i <= start + length - 1; ++i)
{
process.stdout.write(text.charAt(i));
}
// Display length of resultant palindrome
process.stdout.write("\n Resultant length : " + length);
}
}

function main()
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
main();

#### Output

Given string : nitiiiigi
Result : iiii
Resultant length : 4
Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5
Given string : xyzacivicxrs
Result : civic
Resultant length : 5
Given string : ttoopo
Result : opo
Resultant length : 3
#  Python 3 program for
#  Longest palindromic substring using dynamic programming
class LongestPalindrome :
def findLPS(self, text) :
#  Get length of text
n = len(text)
if (n == 0) :
#  When text is empty
return

length = 1
start = 0
dp = [[0] * (n) for _ in range(n) ]
i = 0
#  Set diagonal elements value is 1
while (i < n) :
dp[i][i] = 1
i += 1

i = 0
while (i < n - 1) :
if (text[i] == text[i + 1]) :
#  When adjacent elements is similar
dp[i][i + 1] = 1
#  Change resultant length
length = 2
start = i

i += 1

k = 3
while (k <= n) :
i = 0
while (i < n - k + 1) :
j = i + k - 1
if (dp[i + 1][j - 1] != 0 and text[i] == text[j]) :
dp[i][j] = 1
if (k > length) :
#  Change resultant length
length = k
#  Update resultant starting location
start = i

i += 1

k += 1

#  Display given text
print("\n Given string : ", text, end = "")
print("\n Result : ", end = "")
i = start
#  Display resultant palindrome
while (i <= start + length - 1) :
print(text[i], end = "")
i += 1

#  Display length of resultant palindrome
print("\n Resultant length : ", length, end = "")

def main() :
#  Test
#  iiii => 4
#  ivfvi => 5
#  civic => 5
#  opo => 3

if __name__ == "__main__": main()

#### Output

Given string :  nitiiiigi
Result : iiii
Resultant length :  4
Given string :  vvvvivfvim
Result : ivfvi
Resultant length :  5
Given string :  xyzacivicxrs
Result : civic
Resultant length :  5
Given string :  ttoopo
Result : opo
Resultant length :  3
#  Ruby program for
#  Longest palindromic substring using dynamic programming
class LongestPalindrome
def findLPS(text)
#  Get length of text
n = text.length
if (n == 0)
#  When text is empty
return
end

length = 1
start = 0
dp = Array.new(n) {Array.new(n) {0}}
i = 0
#  Set diagonal elements value is 1
while (i < n)
dp[i][i] = 1
i += 1
end

i = 0
while (i < n - 1)
if (text[i] == text[i + 1])
#  When adjacent elements is similar
dp[i][i + 1] = 1
#  Change resultant length
length = 2
start = i
end

i += 1
end

k = 3
while (k <= n)
i = 0
while (i < n - k + 1)
j = i + k - 1
if (dp[i + 1][j - 1] != 0 && text[i] == text[j])
dp[i][j] = 1
if (k > length)
#  Change resultant length
length = k
#  Update resultant starting location
start = i
end

end

i += 1
end

k += 1
end

#  Display given text
print("\n Given string : ", text)
print("\n Result : ")
i = start
#  Display resultant palindrome
while (i <= start + length - 1)
print(text[i])
i += 1
end

#  Display length of resultant palindrome
print("\n Resultant length : ", length)
end

end

def main()
#  Test
#  iiii => 4
#  ivfvi => 5
#  civic => 5
#  opo => 3
end

main()

#### Output

Given string : nitiiiigi
Result : iiii
Resultant length : 4
Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5
Given string : xyzacivicxrs
Result : civic
Resultant length : 5
Given string : ttoopo
Result : opo
Resultant length : 3
// Scala program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome()
{
def findLPS(text: String): Unit = {
// Get length of text
var n: Int = text.length();
if (n == 0)
{
// When text is empty
return;
}
var length: Int = 1;
var start: Int = 0;
var dp: Array[Array[Int]] = Array.fill[Int](n, n)(0);
var i: Int = 0;
// Set diagonal elements value is 1
while (i < n)
{
dp(i)(i) = 1;
i += 1;
}
i = 0;
while (i < n - 1)
{
if (text.charAt(i) == text.charAt(i + 1))
{
// When adjacent elements is similar
dp(i)(i + 1) = 1;
// Change resultant length
length = 2;
start = i;
}
i += 1;
}
var k: Int = 3;
while (k <= n)
{
i = 0;
while (i < n - k + 1)
{
var j: Int = i + k - 1;
if (dp(i + 1)(j - 1) != 0 &&
text.charAt(i) == text.charAt(j))
{
dp(i)(j) = 1;
if (k > length)
{
// Change resultant length
length = k;
// Update resultant starting location
start = i;
}
}
i += 1;
}
k += 1;
}
// Display given text
print("\n Given string : " + text);
print("\n Result : ");
i = start;
// Display resultant palindrome
while (i <= start + length - 1)
{
print(text.charAt(i));
i += 1;
}
// Display length of resultant palindrome
print("\n Resultant length : " + length);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: LongestPalindrome = new LongestPalindrome();
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
}

#### Output

Given string : nitiiiigi
Result : iiii
Resultant length : 4
Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5
Given string : xyzacivicxrs
Result : civic
Resultant length : 5
Given string : ttoopo
Result : opo
Resultant length : 3
import Foundation;
// Swift 4 program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
func findLPS(_ data: String)
{
let text = Array(data);
// Get length of text
let n: Int = text.count;
if (n == 0)
{
// When text is empty
return;
}
var length: Int = 1;
var start: Int = 0;
var dp: [[Int]] =
Array(repeating: Array(repeating: 0, count: n), count: n);
var i: Int = 0;
// Set diagonal elements value is 1
while (i < n)
{
dp[i][i] = 1;
i += 1;
}
i = 0;
while (i < n - 1)
{
if (text[i] == text[i + 1])
{
// When adjacent elements is similar
dp[i][i + 1] = 1;
// Change resultant length
length = 2;
start = i;
}
i += 1;
}
var k: Int = 3;
while (k <= n)
{
i = 0;
while (i < n - k + 1)
{
let j: Int = i + k - 1;
if (dp[i + 1][j - 1]  != 0 && text[i] == text[j])
{
dp[i][j] = 1;
if (k > length)
{
// Change resultant length
length = k;
// Update resultant starting location
start = i;
}
}
i += 1;
}
k += 1;
}
// Display given text
print("\n Given string : ", data, terminator: "");
print("\n Result : ", terminator: "");
i = start;
// Display resultant palindrome
while (i <= start + length - 1)
{
print(text[i], terminator: "");
i += 1;
}
// Display length of resultant palindrome
print("\n Resultant length : ", length, terminator: "");
}
}
func main()
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}
main();

#### Output

Given string :  nitiiiigi
Result : iiii
Resultant length :  4
Given string :  vvvvivfvim
Result : ivfvi
Resultant length :  5
Given string :  xyzacivicxrs
Result : civic
Resultant length :  5
Given string :  ttoopo
Result : opo
Resultant length :  3
// Kotlin program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
fun findLPS(text: String): Unit
{
// Get length of text
val n: Int = text.length;
if (n == 0)
{
// When text is empty
return;
}
var length: Int = 1;
var start: Int = 0;
val dp: Array < Array < Int >> = Array(n)
{
Array(n)
{
0
}
};
var i: Int = 0;
// Set diagonal elements value is 1
while (i < n)
{
dp[i][i] = 1;
i += 1;
}
i = 0;
while (i < n - 1)
{
if (text.get(i) == text.get(i + 1))
{
// When adjacent elements is similar
dp[i][i + 1] = 1;
// Change resultant length
length = 2;
start = i;
}
i += 1;
}
var k: Int = 3;
while (k <= n)
{
i = 0;
while (i < n - k + 1)
{
val j: Int = i + k - 1;
if (dp[i + 1][j - 1] != 0 && text.get(i) == text.get(j))
{
dp[i][j] = 1;
if (k > length)
{
// Change resultant length
length = k;
// Update resultant starting location
start = i;
}
}
i += 1;
}
k += 1;
}
// Display given text
print("\n Given string : " + text);
print("\n Result : ");
i = start;
// Display resultant palindrome
while (i <= start + length - 1)
{
print(text.get(i));
i += 1;
}
// Display length of resultant palindrome
print("\n Resultant length : " + length);
}
}
fun main(args: Array < String > ): Unit
{
// Test
// iiii => 4
// ivfvi => 5
// civic => 5
// opo => 3
}

#### Output

Given string : nitiiiigi
Result : iiii
Resultant length : 4
Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5
Given string : xyzacivicxrs
Result : civic
Resultant length : 5
Given string : ttoopo
Result : opo
Resultant length : 3

## Resultant Output Explanation

Let's understand the output generated by the code for the given test cases:

Given string : nitiiiigi
Result : iiii
Resultant length : 4

Given string : vvvvivfvim
Result : ivfvi
Resultant length : 5

Given string : xyzacivicxrs
Result : civic
Resultant length : 5

Given string : ttoopo
Result : opo
Resultant length : 3

In the first test case, the input string "nitiiiigi" contains the longest palindromic substring "iiii", which has a length of 4. The second test case "vvvvivfvim" has "ivfvi" as the longest palindromic substring with a length of 5. Similarly, the third test case "xyzacivicxrs" has "civic" as the longest palindromic substring with a length of 5. Finally, in the fourth test case "ttoopo", the longest palindromic substring is "opo" with a length of 3.

## Time Complexity

The time complexity of the dynamic programming solution to find the longest palindromic substring is O(n^2), where n is the length of the input string. This is because we iterate over all substrings of lengths ranging from 3 to n and compare characters within each substring. The nested loops and comparisons contribute to the quadratic time complexity.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post