DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Longest Common Substring Algorithm in Java

Longest Common Substring Algorithm in Java

Peter Karussell user avatar by
Peter Karussell
·
Apr. 15, 11 · Interview
Like (0)
Save
Tweet
Share
20.53K Views

Join the DZone community and get the full member experience.

Join For Free

For jetwick I needed yet another string algorithm and stumbled over this cool and common problem: trying to find the longest substring of two strings. Be sure that you understand the difference to the LC sequence problem.

For example if we have two strings:

Please, peter go swimming!

and

I’m peter goliswi

The algorithm should print out ‘ peter go’. The longest common substring algorithm can be implemented in an efficient manner with the help of suffic trees.

But in this post I’ll try to explain the bit less efficient ‘dynamic programming‘ version of the algorithm. Dynamic programming means that you can reuse already calculated information in a later step or you break the algorithm into parts to reuse information. To understand the algorithm you just need to fill the entries of an integer-array with the lengths of the identical substrings. Assume we use i for the horizontal string (please …) and j for the vertical string. Then the algorithm hits at some time i=19 and j=0 for one identical character ‘i’. Then the line

num[i][j] = 1;

is executed and saves the lengths of the 1 length identical substring.

  please, peter go swimming
i 0000000000000000000100100
' 0000000000000000000000000
m 0000000000000000000011000
0000000100000100100000000
p 1000000020000000000000000
e 0010010003000000000000000
t 0000000000400000000000000
e 0010010001050000000000000
r 0000000000006000000000000
0000000100000700100000000
g 0000000000000080000000000
o 0000000000000009000000000
l 0100000000000000000000000
i 0000000000000000000100100
s 0001000000000000010000000
w 0000000000000000002000000
i 0000000000000000000300100

Later on it hits the m characters and saves 1 two times to the array but then at i=7 and j=3 it starts our substring and saves 1 for the space character. Then some loops later it reaches i=8 and j=4  Now it reuses the already calculated “identical-length” of 1. It will do:

num[8][4] = 1 + num[7][3];

and we get 2. So, we now know we have a substring with two 2 characters. And with

if (num[i][j] > maxlen)

we make sure that we overwrite the existing longest substring (stored in the StringBuilder) ONLY IF there is a longer substring found and either append the character (if it is the current substring in progress):

sb.append(str1.charAt(i));

or we can start a longer substring. See the java code (mainly taken from wikipedia) for yourself:

public static String longestSubstring(String str1, String str2) {

StringBuilder sb = new StringBuilder();
if (str1 == null || str1.isEmpty() || str2 == null || str2.isEmpty())
return "";

// ignore case
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();

// java initializes them already with 0
int[][] num = new int[str1.length()][str2.length()];
int maxlen = 0;
int lastSubsBegin = 0;

for (int i = 0; i < str1.length(); i++) {
for (int j = 0; j < str2.length(); j++) {
if (str1.charAt(i) == str2.charAt(j)) {
if ((i == 0) || (j == 0))
num[i][j] = 1;
else
num[i][j] = 1 + num[i - 1][j - 1];

if (num[i][j] > maxlen) {
maxlen = num[i][j];
// generate substring from str1 => i
int thisSubsBegin = i - num[i][j] + 1;
if (lastSubsBegin == thisSubsBegin) {
//if the current LCS is the same as the last time this block ran
sb.append(str1.charAt(i));
} else {
//this block resets the string builder if a different LCS is found
lastSubsBegin = thisSubsBegin;
sb = new StringBuilder();
sb.append(str1.substring(lastSubsBegin, i + 1));
}
}
}
}}

return sb.toString();
}

 

From http://karussell.wordpress.com/2011/04/14/longest-common-substring-algorithm-in-java/

Algorithm Java (programming language)

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • How To Choose the Right Streaming Database
  • Seamless Integration of Azure Functions With SQL Server: A Developer's Perspective
  • Building the Next-Generation Data Lakehouse: 10X Performance
  • How To Create a Failover Client Using the Hazelcast Viridian Serverless

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: