public class LCSDemo
1: //LCSDemo.java
3: import java.util.Scanner;
5: public class LCSDemo
6: {
7: static String longestCommonSubstring
8: (
9: String str1,
10: String str2
11: )
12: {
13: // Allocate the matrix.
14: int[][] matrix = new int[str1.length()][str2.length()];
16: // Variables to remember the largest value, and the position it
17: // occurred at.
18: int maxValue = 0;
19: int maxValueRow = 0;
20: int maxValueCol = 0;
21: for (int row = 0; row < str1.length(); row++)
22: {
23: for (int col = 0; col < str2.length(); col++)
24: {
25: // Check if the characters match
26: if (str1.charAt(row) == str2.charAt(col))
27: {
28: // Get the value in the cell that's up and to the
29: // left, or 0 if no such cell
30: int upLeft = 0;
31: if (row > 0 && col > 0)
32: {
33: upLeft = matrix[row - 1][col - 1];
34: }
36: // Set the value for this cell
37: matrix[row][col] = 1 + upLeft;
38: if (matrix[row][col] > maxValue)
39: {
40: maxValue = matrix[row][col];
41: maxValueRow = row;
42: maxValueCol = col;
43: }
44: }
45: else
46: {
47: matrix[row][col] = 0;
48: }
49: }
50: }
52: // Return the longest common substring
53: int startIndex = maxValueRow - maxValue + 1;
54: return str1.substring(startIndex, startIndex + maxValue);
55: }
57: static String longestCommonSubstringOptimized
58: (
59: String str1,
60: String str2
61: )
62: {
63: // Create one row of the matrix.
64: int[] matrixRow = new int[str2.length()];
66: // Variables to remember the largest value, and the row it
67: // occurred at.
68: int maxValue = 0;
69: int maxValueRow = 0;
70: for (int row = 0; row < str1.length(); row++)
71: {
72: // Variable to hold the upper-left value from the
73: // current matrix position.
74: int upLeft = 0;
75: for (int col = 0; col < str2.length(); col++)
76: {
77: // Save the current cell's value; this will be upLeft
78: // for the next iteration.
79: int savedCurrent = matrixRow[col];
81: // Check if the characters match
82: if (str1.charAt(row) == str2.charAt(col))
83: {
84: matrixRow[col] = 1 + upLeft;
86: // Update the saved maximum value and row,
87: // if appropriate.
88: if (matrixRow[col] > maxValue)
89: {
90: maxValue = matrixRow[col];
91: maxValueRow = row;
92: }
93: }
94: else
95: {
96: matrixRow[col] = 0;
97: }
99: // Update the upLeft variable
100: upLeft = savedCurrent;
101: }
102: }
104: // The longest common substring is the substring
105: // in str1 from index maxValueRow - maxValue + 1,
106: // up to and including maxValueRow.
107: int startIndex = maxValueRow - maxValue + 1;
108: return str1.substring(startIndex, maxValueRow + 1);
109: }
111: public static void main(String[] args)
112: {
113: // Main program to test the longest common substring algorithms.
115: Scanner scnr = new Scanner(System.in);
116: System.out.print("Enter the first string: ");
117: String firstString = scnr.nextLine();
118: System.out.print("Enter the second string: ");
119: String secondString = scnr.nextLine();
120: System.out.println();
122: String unoptimized = longestCommonSubstring
123: (
124: firstString,
125: secondString
126: );
127: String optimized = longestCommonSubstringOptimized
128: (
129: firstString,
130: secondString
131: );
132: System.out.println();
133: System.out.println("Unoptimized solution: " + unoptimized);
134: System.out.println("Optimized solution: " + optimized);
135: }
136: }