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) | – |