算法实现/字符串/最长公共子字符串
最长公共子字符串算法的常见动态规划实现运行时间为 O(nm)。所有这些实现都使用 O(nm) 的存储空间。细心的读者会注意到，在计算下一列时，实际上只使用了存储动态状态的上一列网格。因此，可以修改这些算法，使其仅具有 O(n) 的存储空间要求。通过在两个一维数组之间重新分配数组引用，可以在不将状态数据从一个数组复制到另一个数组的情况下实现这一点。我可能会回来更新此页面；目前，此优化留给读者作为练习。
对于较大的 n，存在基于滚动哈希的更快算法，其运行时间为 O(n log n)，存储空间要求为 O(n log n)。
后缀树可用于以额外存储空间和算法复杂性的代价实现 O(n+m) 的运行时间。
func LCS(s1 string, s2 string) string {
var m = make([][]int, 1 + len(s1))
for i := 0; i < len(m); i++ {
m[i] = make([]int, 1 + len(s2))
}
longest := 0
x_longest := 0
for x := 1; x < 1 + len(s1); x++ {
for y := 1; y < 1 + len(s2); y++ {
if s1[x-1] == s2[y-1] {
m[x][y] = m[x-1][y-1] + 1
if m[x][y] > longest {
longest = m[x][y]
x_longest = x
}
}
}
}
return s1[x_longest - longest: x_longest]
}
给定两个非空字符串作为参数，此方法将返回两个参数共有的最长子字符串的长度。下面有一个变体，返回实际的字符串。
public int LongestCommonSubstring(string str1, string str2)
{
if (String.IsNullOrEmpty(str1) || String.IsNullOrEmpty(str2))
return 0;
int[,] num = new int[str1.Length, str2.Length];
int maxlen = 0;
for (int i = 0; i < str1.Length; i++)
{
for (int j = 0; j < str2.Length; j++)
{
if (str1[i] != str2[j])
num[i, j] = 0;
else
{
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];
}
}
}
}
return maxlen;
}
此示例使用 out 关键字传递字符串引用，方法将把该引用设置为包含最长公共子字符串的字符串。
public int LongestCommonSubstring(string str1, string str2, out string sequence)
{
sequence = string.Empty;
if (String.IsNullOrEmpty(str1) || String.IsNullOrEmpty(str2))
return 0;
int[,] num = new int[str1.Length, str2.Length];
int maxlen = 0;
int lastSubsBegin = 0;
StringBuilder sequenceBuilder = new StringBuilder();
for (int i = 0; i < str1.Length; i++)
{
for (int j = 0; j < str2.Length; j++)
{
if (str1[i] != str2[j])
num[i, j] = 0;
else
{
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];
int thisSubsBegin = i - num[i, j] + 1;
if (lastSubsBegin == thisSubsBegin)
{//if the current LCS is the same as the last time this block ran
sequenceBuilder.Append(str1[i]);
}
else //this block resets the string builder if a different LCS is found
{
lastSubsBegin = thisSubsBegin;
sequenceBuilder.Length = 0; //clear it
sequenceBuilder.Append(str1.Substring(lastSubsBegin, (i + 1) - lastSubsBegin));
}
}
}
}
}
sequence = sequenceBuilder.ToString();
return maxlen;
}
此方法中的额外复杂性使创建的新字符串对象数量最少。这在 C# 中很重要，因为字符串是不可变的：每次将字符串字段赋值时，旧字符串都会保留在内存中，直到垃圾收集器运行。因此，在保持新字符串数量尽可能少方面付出了努力。
通过仅跟踪字符串的起始位置（例如在 str1 中，或在 str1 和 str2 中），算法可以简化（留给读者作为练习），并让调用者使用此位置和返回的长度来提取字符串。这样的变体也可能更有用，因为主题字符串中的实际位置将被识别出来。
#include "iostream"
using namespace std;
char **A;
int main(int argc, char* argv[])
{
int satir, sira=1;
cin >> satir;
A = new char *[satir];
for(int i=0; i<satir; i++)
*(A+i)= new char [sira];
for(int j=1; j<=satir; j++)
cin >> A[0][j];
for(int j=1; j<=satir; j++)
cout << A[0][j];
cin >> sira;
for(int i=1; i<=sira; i++)
cin >> A[i][0];
for(int j=1; j<=satir; j++)
cout << A[0][j];
for(int i=1;i<=sira;i++){
for(int j=1; j<=satir; j++){
if(A[0][j]==A[i][0]){
cout << A[i][0];
}
}
}
return 0;
}
def longest_common_substring(s1, s2):
m = [[0] * (1 + len(s2)) for i in range (1 + len(s1))]
longest, x_longest = 0, 0
for x in range(1, 1 + len(s1)):
for y in range(1, 1 + len(s2)):
if s1[x - 1] == s2[y - 1]:
m[x][y] = m[x - 1][y - 1] + 1
if m[x][y] > longest:
longest = m[x][y]
x_longest = x
else:
m[x][y] = 0
return s1[x_longest - longest: x_longest]
(defn lcs
[str1 str2]
(loop [s1 (seq str1), s2 (seq str2), len 0, maxlen 0]
(cond
(>= maxlen (count s1)) maxlen
(>= maxlen (+ (count s2) len)) (recur (rest s1) (seq str2) 0 maxlen)
:else (let [a (nth s1 len ""), [b & s2] s2, len (inc len)]
(if (= a b)
(recur s1 s2 len (if (> len maxlen) len maxlen))
(recur s1 s2 0 maxlen))))))
sub lc_substr {
my ($str1, $str2) = @_;
my $l_length = 0; # length of longest common substring
my $len1 = length $str1;
my $len2 = length $str2;
my @char1 = (undef, split(//, $str1)); # $str1 as array of chars, indexed from 1
my @char2 = (undef, split(//, $str2)); # $str2 as array of chars, indexed from 1
my @lc_suffix; # "longest common suffix" table
my @substrings; # list of common substrings of length $l_length
for my $n1 ( 1 .. $len1 ) {
for my $n2 ( 1 .. $len2 ) {
if ($char1[$n1] eq $char2[$n2]) {
# We have found a matching character. Is this the first matching character, or a
# continuation of previous matching characters? If the former, then the length of
# the previous matching portion is undefined; set to zero.
$lc_suffix[$n1-1][$n2-1] ||= 0;
# In either case, declare the match to be one character longer than the match of
# characters preceding this character.
$lc_suffix[$n1][$n2] = $lc_suffix[$n1-1][$n2-1] + 1;
# If the resulting substring is longer than our previously recorded max length ...
if ($lc_suffix[$n1][$n2] > $l_length) {
# ... we record its length as our new max length ...
$l_length = $lc_suffix[$n1][$n2];
# ... and clear our result list of shorter substrings.
@substrings = ();
}
# If this substring is equal to our longest ...
if ($lc_suffix[$n1][$n2] == $l_length) {
# ... add it to our list of solutions.
push @substrings, substr($str1, ($n1-$l_length), $l_length);
}
}
}
}
return @substrings;
}
Function LongestCommonSubstring(S1 As String, S2 As String) As String
MaxSubstrStart = 1
MaxLenFound = 0
For i1 = 1 To Len(S1)
For i2 = 1 To Len(S2)
X = 0
While i1 + X <= Len(S1) And _
i2 + X <= Len(S2) And _
Mid(S1, i1 + X, 1) = Mid(S2, i2 + X, 1)
X = X + 1
Wend
If X > MaxLenFound Then
MaxLenFound = X
MaxSubstrStart = i1
End If
Next
Next
LongestCommonSubstring = Mid(S1, MaxSubstrStart, MaxLenFound)
End Function
Public Function LongestCommonSubstring(ByVal s1 As String, ByVal s2 As String) As Integer
Dim num(s1.Length - 1, s2.Length - 1) As Integer '2D array
Dim letter1 As Char = Nothing
Dim letter2 As Char = Nothing
Dim len As Integer = 0
Dim ans As Integer = 0
For i As Integer = 0 To s1.Length - 1
For j As Integer = 0 To s2.Length - 1
letter1 = s1.Chars(i)
letter2 = s2.Chars(j)
If Not letter1.Equals(letter2) Then
num(i, j) = 0
Else
If i.Equals(0) Or j.Equals(0) Then
num(i, j) = 1
Else
num(i, j) = 1 + num(i - 1, j - 1)
End If
If num(i, j) > len Then
len = num(i, j)
ans = num(i, j)
End If
End If
Next j
Next i
Return ans
End Function
此算法不使用额外存储空间，但运行时间为 O(mnl)。要比较的两个字符串应放置在 WS-TEXT1 和 WS-TEXT2 中，它们的长度分别放置在 WS-LEN1 和 WS-LEN2 中。此例程的输出是 MAX-LEN，即最大公共子字符串的长度，WS-LOC1，即它在 WS-TEXT1 中的起始位置，以及 WS-LOC2，即它在 WS-TEXT2 中的起始位置。
01 MAX-LEN PIC 9999 COMP.
01 WS-IX1 PIC 9999 COMP.
01 WS-IX2 PIC 9999 COMP.
01 WK-LEN PIC 9999 COMP.
01 WS-LOC1 PIC 9999 COMP.
01 WS-LOC2 PIC 9999 COMP.
01 WS-FLAG PIC X.
88 NO-DIFFERENCE-FOUND VALUE 'N'.
88 DIFFERENCE-FOUND VALUE 'Y'.
MOVE ZERO TO MAX-LEN.
PERFORM VARYING WS-IX1 FROM 1 BY 1 UNTIL WS-IX1 > WS-LEN1
PERFORM VARYING WS-IX2 FROM 1 BY 1 UNTIL WS-IX2 > WS-LEN2
SET NO-DIFFERENCE-FOUND TO TRUE
PERFORM VARYING WK-LEN FROM MAX-LEN BY 1 UNTIL
WS-IX1 + WK-LEN > WS-LEN1 OR
WS-IX2 + WK-LEN > WS-LEN2 OR
DIFFERENCE-FOUND
IF WS-TEXT1(WS-IX1 : WK-LEN + 1) = WS-TEXT2(WS-IX2 : WK-LEN + 1)
COMPUTE MAX-LEN = WK-LEN + 1
MOVE WS-IX1 TO WS-LOC1
MOVE WS-IX2 TO WS-LOC2
ELSE
SET DIFFERENCE-FOUND TO TRUE
END-IF
END-PERFORM
END-PERFORM
END-PERFORM.
#include <string>
using std::string;
int LongestCommonSubstring(const string& str1, const string& str2)
{
if(str1.empty() || str2.empty())
{
return 0;
}
int *curr = new int [str2.size()];
int *prev = new int [str2.size()];
int *swap = nullptr;
int maxSubstr = 0;
for(int i = 0; i<str1.size(); ++i)
{
for(int j = 0; j<str2.size(); ++j)
{
if(str1[i] != str2[j])
{
curr[j] = 0;
}
else
{
if(i == 0 || j == 0)
{
curr[j] = 1;
}
else
{
curr[j] = 1 + prev[j-1];
}
//The next if can be replaced with:
//maxSubstr = max(maxSubstr, curr[j]);
//(You need algorithm.h library for using max())
if(maxSubstr < curr[j])
{
maxSubstr = curr[j];
}
}
}
swap=curr;
curr=prev;
prev=swap;
}
delete [] curr;
delete [] prev;
return maxSubstr;
}
class String
def intersection(str)
return '' if [self, str].any?(&:empty?)
matrix = Array.new(self.length) { Array.new(str.length) { 0 } }
intersection_length = 0
intersection_end = 0
self.length.times do |x|
str.length.times do |y|
next unless self[x] == str[y]
matrix[x][y] = 1 + (([x, y].all?(&:zero?)) ? 0 : matrix[x-1][y-1])
next unless matrix[x][y] > intersection_length
intersection_length = matrix[x][y]
intersection_end = x
end
end
intersection_start = intersection_end - intersection_length + 1
slice(intersection_start..intersection_end)
end
end
public static int longestSubstr(String first, String second) {
int maxLen = 0;
int fl = first.length();
int sl = second.length();
int[][] table = new int[fl+1][sl+1];
for (int i = 1; i <= fl; i++) {
for (int j = 1; j <= sl; j++) {
if (first.charAt(i-1) == second.charAt(j-1)) {
table[i][j] = table[i - 1][j - 1] + 1;
if (table[i][j] > maxLen)
maxLen = table[i][j];
}
}
}
return maxLen;
}
- Java 对 C# 代码的调整，用于检索最长子字符串
private static String longestCommonSubstring(String S1, String S2)
{
int Start = 0;
int Max = 0;
for (int i = 0; i < S1.length(); i++)
{
for (int j = 0; j < S2.length(); j++)
{
int x = 0;
while (S1.charAt(i + x) == S2.charAt(j + x))
{
x++;
if (((i + x) >= S1.length()) || ((j + x) >= S2.length())) break;
}
if (x > Max)
{
Max = x;
Start = i;
}
}
}
return S1.substring(Start, (Start + Max));
}
public static int longestSubstr(String s, String t) {
if (s.isEmpty() || t.isEmpty()) {
return 0;
}
int m = s.length();
int n = t.length();
int cost = 0;
int maxLen = 0;
int[] p = new int[n];
int[] d = new int[n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// calculate cost/score
if (s.charAt(i) != t.charAt(j)) {
cost = 0;
} else {
if ((i == 0) || (j == 0)) {
cost = 1;
} else {
cost = p[j - 1] + 1;
}
}
d[j] = cost;
if (cost > maxLen) {
maxLen = cost;
}
} // for {}
int[] swap = p;
p = d;
d = swap;
}
return maxLen;
}
function longestCommonSubstring(string1, string2){
// init max value
var longestCommonSubstring = 0;
// init 2D array with 0
var table = [],
len1 = string1.length,
len2 = string2.length,
row, col;
for(row = 0; row <= len1; row++){
table[row] = [];
for(col = 0; col <= len2; col++){
table[row][col] = 0;
}
}
// fill table
var i, j;
for(i = 0; i < len1; i++){
for(j = 0; j < len2; j++){
if(string1[i] === string2[j]){
if(table[i][j] === 0){
table[i+1][j+1] = 1;
} else {
table[i+1][j+1] = table[i][j] + 1;
}
if(table[i+1][j+1] > longestCommonSubstring){
longestCommonSubstring = table[i+1][j+1];
}
} else {
table[i+1][j+1] = 0;
}
}
}
return longestCommonSubstring;
}
变体，返回最长公共子字符串和偏移量以及长度
function longestCommonSubstring(str1, str2){
if (!str1 || !str2)
return {
length: 0,
sequence: "",
offset: 0
};
var sequence = "",
str1Length = str1.length,
str2Length = str2.length,
num = new Array(str1Length),
maxlen = 0,
lastSubsBegin = 0;
for (var i = 0; i < str1Length; i++) {
var subArray = new Array(str2Length);
for (var j = 0; j < str2Length; j++)
subArray[j] = 0;
num[i] = subArray;
}
var thisSubsBegin = null;
for (var i = 0; i < str1Length; i++)
{
for (var j = 0; j < str2Length; j++)
{
if (str1[i] !== str2[j])
num[i][j] = 0;
else
{
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];
thisSubsBegin = i - num[i][j] + 1;
if (lastSubsBegin === thisSubsBegin)
{//if the current LCS is the same as the last time this block ran
sequence += str1[i];
}
else //this block resets the string builder if a different LCS is found
{
lastSubsBegin = thisSubsBegin;
sequence= ""; //clear it
sequence += str1.substr(lastSubsBegin, (i + 1) - lastSubsBegin);
}
}
}
}
}
return {
length: maxlen,
sequence: sequence,
offset: thisSubsBegin
};
}
与页面上其他算法的蛮力算法类似，但存储空间为 O(2n)，而其他实现需要 O(mn) 的存储空间
export function longestCommonSubstr (str1: string, str2: string) {
if (!str1 || !str2) { return '' }
const str1Length = str1.length
const str2Length = str2.length
let maxLength = 0
let beginIndx = 0 // relative to str1
const num = [new Array(str2Length), ([] as number[]).fill(0, 0, -str2Length)] as [number[], number[]]
for (let i = 0; i < str1Length; ++i) {
const lastRow = 1 - i % 2
const currentRow = num[1 - lastRow]
for (let j = 0; j < str2Length; ++j) {
if (str1[i] !== str2[j]) {
currentRow[j] = 0
} else {
if (i === 0 || j === 0) {
currentRow[j] = 1
} else {
currentRow[j] = 1 + num[lastRow][j - 1]
}
if (currentRow[j] > maxLength) {
maxLength = currentRow[j]
beginIndx = i - currentRow[j] + 1
// if the current LCS is the same as the last time this block ran
}
}
}
}
return str1.slice(beginIndx, maxLength + beginIndx)
}
function lcs(string a, b)
integer longest = 0
string best = ""
for i=1 to length(a) do
integer ch = a[i]
for j=1 to length(b) do
if ch=b[j] then
integer n=1
while i+n<=length(a)
and j+n<=length(b)
and a[i+n]=b[j+n] do
n += 1
end while
if n>longest then
longest = n
best = a[i..i+n-1]
end if
end if
end for
end for
return best
end function
function get_longest_common_subsequence($string_1, $string_2)
{
$string_1_length = strlen($string_1);
$string_2_length = strlen($string_2);
$return = '';
if ($string_1_length === 0 || $string_2_length === 0)
{
// No similarities
return $return;
}
$longest_common_subsequence = array();
// Initialize the CSL array to assume there are no similarities
$longest_common_subsequence = array_fill(0, $string_1_length, array_fill(0, $string_2_length, 0));
$largest_size = 0;
for ($i = 0; $i < $string_1_length; $i++)
{
for ($j = 0; $j < $string_2_length; $j++)
{
// Check every combination of characters
if ($string_1[$i] === $string_2[$j])
{
// These are the same in both strings
if ($i === 0 || $j === 0)
{
// It's the first character, so it's clearly only 1 character long
$longest_common_subsequence[$i][$j] = 1;
}
else
{
// It's one character longer than the string from the previous character
$longest_common_subsequence[$i][$j] = $longest_common_subsequence[$i - 1][$j - 1] + 1;
}
if ($longest_common_subsequence[$i][$j] > $largest_size)
{
// Remember this as the largest
$largest_size = $longest_common_subsequence[$i][$j];
// Wipe any previous results
$return = '';
// And then fall through to remember this new value
}
if ($longest_common_subsequence[$i][$j] === $largest_size)
{
// Remember the largest string(s)
$return = substr($string_1, $i - $largest_size + 1, $largest_size);
}
}
// Else, $CSL should be set to 0, which it was already initialized to
}
}
// Return the list of matches
return $return;
}
function GetLongestSubstring(lcString1, lcString2)
Local lnLenString1, lnLenString2, lnMaxlen, lnLastSubStart, lnThisSubStart, i, j
Local lcLetter1, lcLetter2, lcSequence
Store Space(0) TO lcLetter1, lcLetter2, lcSequence
Store 0 TO lnLenString1, lnLenString2, lnMaxlen, lnLastSubStart, lnThisSubStart, i, j, laNum
lnLenString1 = Len(lcString1)
lnLenString2 = Len(lcString2)
Dimension laNum(lnLenString1,lnLenString2)
For i = 1 To lnLenString1
For j = 1 To lnLenString2
lcLetter1 = Substr(lcString1,i,1)
lcLetter2 = Substr(lcString2,j,1)
If !lcLetter1 == lcLetter2
laNum(i, j) = 0
Else
If i=1 OR j=1
laNum(i, j) = 1
Else
laNum(i, j) = 1 + laNum(i - 1, j - 1)
Endif
If laNum(i, j) > lnMaxlen
lnMaxlen = laNum(i, j)
lnThisSubStart = i - laNum[i, j] + 1
If (lnLastSubStart == lnThisSubStart)
lcSequence = lcSequence + lcLetter1
Else
lnLastSubStart = lnThisSubStart
lcSequence = Space(0)
lcSequence = Substr(lcString1,lnLastSubStart,(i + 1) - lnLastSubStart)
Endif
Endif
Endif
Next
Next
Return(lcSequence)
import Data.List
import Data.Function
lcstr xs ys = maximumBy (compare `on` length) . concat $ [f xs' ys | xs' <- tails xs] ++ [f xs ys' | ys' <- drop 1 $ tails ys]
where f xs ys = scanl g [] $ zip xs ys
g z (x, y) = if x == y then z ++ [x] else []
(defun longest-common-substring (a b)
(let ((L (make-array (list (length a) (length b)) :initial-element 0))
(z 0)
(result '()))
(dotimes (i (length a))
(dotimes (j (length b))
(when (char= (char a i) (char b j))
(setf (aref L i j)
(if (or (zerop i) (zerop j))
1
(1+ (aref L (1- i) (1- j)))))
(when (> (aref L i j) z)
(setf z (aref L i j)
result '()))
(when (= (aref L i j) z)
(pushnew (subseq a (1+ (- i z)) (1+ i))
result :test #'equal)))))
result))
+ (NSString *)longestCommonSubstring:(NSString *)substring string:(NSString *)string {
if (substring == nil || substring.length == 0 || string == nil || string.length == 0) {
return nil;
}
NSMutableDictionary *map = [NSMutableDictionary dictionary];
int maxlen = 0;
int lastSubsBegin = 0;
NSMutableString *sequenceBuilder = [NSMutableString string];
for (int i = 0; i < substring.length; i++)
{
for (int j = 0; j < string.length; j++)
{
unichar substringC = [[substring lowercaseString] characterAtIndex:i];
unichar stringC = [[string lowercaseString] characterAtIndex:j];
if (substringC != stringC) {
[map setObject:[NSNumber numberWithInt:0] forKey:[NSString stringWithFormat:@"%i%i",i,j]];
}
else {
if ((i == 0) || (j == 0)) {
[map setObject:[NSNumber numberWithInt:1] forKey:[NSString stringWithFormat:@"%i%i",i,j]];
}
else {
int prevVal = [[map objectForKey:[NSString stringWithFormat:@"%i%i",i-1,j-1]] intValue];
[map setObject:[NSNumber numberWithInt:1+prevVal] forKey:[NSString stringWithFormat:@"%i%i",i,j]];
}
int currVal = [[map objectForKey:[NSString stringWithFormat:@"%i%i",i,j]] intValue];
if (currVal > maxlen) {
maxlen = currVal;
int thisSubsBegin = i - currVal + 1;
if (lastSubsBegin == thisSubsBegin)
{//if the current LCS is the same as the last time this block ran
NSString *append = [NSString stringWithFormat:@"%C",substringC];
[sequenceBuilder appendString:append];
}
else //this block resets the string builder if a different LCS is found
{
lastSubsBegin = thisSubsBegin;
NSString *resetStr = [substring substringWithRange:NSMakeRange(lastSubsBegin, (i + 1) - lastSubsBegin)];
sequenceBuilder = [NSMutableString stringWithFormat:@"%@",resetStr];
}
}
}
}
}
return [sequenceBuilder copy];
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int *lcommon(char *s, char *t) {
int strlen1 = strlen(s);
int strlen2 = strlen(t);
int len = (strlen1 < strlen2) ? strlen2 : strlen1;
int i, j, k;
int longest = 0;
int **ptr = (int **)malloc(2 * sizeof(int *));
static int *ret;
/*
* Maximum length of the return list (considering intermediate steps).
* It is the maximum length of the source strings + 1 (worst-case
* intermediate length) + the value of the longest match + the
* terminator value (-1).
*/
ret = (int *)malloc((len + 3) * sizeof(int));
for (i = 0; i < 2; i++)
ptr[i] = (int *)calloc(strlen2, sizeof(int));
ret[1] = -1;
for (i = 0; i < strlen1; i++) {
memcpy(ptr[0], ptr[1], strlen2 * sizeof(int));
for (j = 0; j < strlen2; j++) {
if (s[i] == t[j]) {
if (i == 0 || j == 0) {
ptr[1][j] = 1;
} else {
ptr[1][j] = ptr[0][j-1] + 1;
}
if (ptr[1][j] > longest) {
longest = ptr[1][j];
k = 1;
}
if (ptr[1][j] == longest) {
ret[k++] = i;
ret[k] = -1;
}
} else {
ptr[1][j] = 0;
}
}
}
for (i = 0; i < 2; i++)
free(ptr[i]);
free(ptr);
/* store the maximum length in ret[0] */
ret[0] = longest;
return ret;
}
int main(int argc, char *argv[]) {
int i, longest, *ret;
if (argc != 3) {
printf("usage: longest-common-substring string1 string2\n");
exit(1);
}
ret = lcommon(argv[1], argv[2]);
if ((longest = ret[0]) == 0) {
printf("There is no common substring\n");
exit(2);
}
i = 0;
while (ret[++i] != -1) {
printf("%.*s\n", longest, &argv[1][ret[i]-longest+1]);
}
free(ret);
exit(0);
}
proc lcs {a b} {
set maxLengthFound 0
set maxSubStart 0
set la [string length $a]
set lb [string length $b]
for {set i 0} {$i < $la} {incr i} {
for {set j 0} {$j < $lb} {incr j} {
for {set x 0} {(($i+$x) < $la) && (($j+$x) < $lb) && ([string index $a [expr $i + $x]] eq [string index $b [expr $j + $x]])} {incr x} {}
if {$x > $maxLengthFound} {
set maxLengthFound $x
set maxSubStart $i
# "we found $maxLengthFound common characters at position $maxSubStart"
}
}
}
return [string range $a $maxSubStart [expr $maxLengthFound + $maxSubStart - 1]]
}