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 Case | Average Case | Worst Case |
---|---|---|
– | O(mn) | – |