Dynamic programming

String matching

Pinterest LinkedIn Tumblr

Write a program for String matching which takes pattern and string.

source Code

package com.dsacode.Algorithm.dynamic;
 
public class StringMatching {
    public static String lcs(String a, String b) {
        int[][] lengths = new int[a.length()+1][b.length()+1];
 
        for (int i = 0; i < a.length(); i++)
            for (int j = 0; j < b.length(); j++)
                if (a.charAt(i) == b.charAt(j))
                    lengths[i+1][j+1] = lengths[i][j] + 1;
                else
                    lengths[i+1][j+1] =
                        Math.max(lengths[i+1][j], lengths[i][j+1]);
      
        StringBuffer sb = new StringBuffer();
        for (int x = a.length(), y = b.length();
             x != 0 && y != 0; ) {
            if (lengths[x][y] == lengths[x-1][y])
                x--;
            else if (lengths[x][y] == lengths[x][y-1])
                y--;
            else {
                assert a.charAt(x-1) == b.charAt(y-1);
                sb.append(a.charAt(x-1));
                x--;
                y--;
            }
        }
      
        return sb.reverse().toString();
    }
    public static void main(String[] args) {
        String str1="HelloWorld";
        String str2="HelloSelvam";
         
        System.out.println("String Matching with '" + str1 +"' and '"+ str2 +"' is " +lcs(str1,str2) +" using dynamic programming!");
 
    }
 
}

Output

String matching with 'HelloWorld' and 'HelloSelvam' is Hellol using dynamic programming!

Algorithm Explanation

Pass string arguments to the utility function.
Create two-dimensional array of integers using the combination of two string length.
Iterate two strings using loop and match with each character.
Create string buffer for appending the matched chars.
If both chars match, it appends to the string buffer. otherwise, ignore the character using Dynamic Programming.
Return the match string and display.

Time Complexity

Best CaseAverage CaseWorst Case
O(mn)

Reference

  1. http://digitalcommons.unf.edu/cgi/viewcontent.cgi?article=1196&context=etd
  2. https://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE46.HTM

Write A Comment