← DiffPush

Longest Common Substring

Standard Bar Dynamic Programming · DP on Strings O(n*m) · O(min(n, m))

The Barcode Segment Matcher

A scanner vendor validates label formats by finding the longest block of glyphs that appears contiguously in two barcode strips. Contiguity is the whole point — a scattered overlap is worthless for calibrating the reader. The calibration utility reports the length of that longest continuous shared block.

Input: Integers n and m, plus strings S1 and S2 of lengths n and m.

Output: Return the length of the longest string that occurs contiguously in both S1 and S2.

Constraints

• 1 <= n, m <= 1000
• strings consist of uppercase English letters

Examples

Example 1

Input: {"n":6,"m":6,"S1":"ABCDGH","S2":"ACDGHR"}
Output: 4
The block "CDGH" runs contiguously through both strings.

Example 2

Input: {"n":4,"m":4,"S1":"abcjklp","S2":"acjkp"}
Output: 3
"cjk" is the longest unbroken shared run.

Solve this in your browser →

Also on LeetCode ↗