Jump to content
Wikibooks The Free Textbook Project

Algorithm Implementation/Strings/Longest common substring

From Wikibooks, open books for an open world

Wikipedia has related information at Longest common substring

Common dynamic programming implementations for the Longest Common Substring algorithm runs in O(nm) time. All of these implementations also use O(nm) storage. The astute reader will notice that only the previous column of the grid storing the dynamic state is ever actually used in computing the next column. Thus, these algorithm can be altered to have only an O(n) storage requirement. By reassigning array references between two 1D arrays, this can be done without copying the state data from one array to another. I may return later and update this page accordingly; for now, this optimization is left as an exercise to the reader.

For large n, faster algorithms based on rolling hashes exist that run in O(n log n) time and require O(n log n) storage.

Suffix trees can be used to achieve a O(n+m) run time at the cost of extra storage and algorithmic complexity. 

funcLCS(s1string,s2string)string{
varm=make([][]int,1+len(s1))
fori:=0;i<len(m);i++{
m[i]=make([]int,1+len(s2))
}
longest:=0
x_longest:=0
forx:=1;x<1+len(s1);x++{
fory:=1;y<1+len(s2);y++{
ifs1[x-1]==s2[y-1]{
m[x][y]=m[x-1][y-1]+1
ifm[x][y]>longest{
longest=m[x][y]
x_longest=x
}
}
}
}
returns1[x_longest-longest:x_longest]
}

Length of Longest Substring

[edit | edit source ]

Given two non-empty strings as parameters, this method will return the length of the longest substring common to both parameters. A variant, below, returns the actual string. 

publicintLongestCommonSubstring(stringstr1,stringstr2)
{
if(String.IsNullOrEmpty(str1)||String.IsNullOrEmpty(str2))
return0;
int[,]num=newint[str1.Length,str2.Length];
intmaxlen=0;
for(inti=0;i<str1.Length;i++)
{
for(intj=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];
}
}
}
}
returnmaxlen;
}

Retrieve the Longest Substring

[edit | edit source ]

This example uses the out keyword to pass in a string reference which the method will set to a string containing the longest common substring. 

publicintLongestCommonSubstring(stringstr1,stringstr2,outstringsequence)
{
sequence=string.Empty;
if(String.IsNullOrEmpty(str1)||String.IsNullOrEmpty(str2))
return0;
int[,]num=newint[str1.Length,str2.Length];
intmaxlen=0;
intlastSubsBegin=0;
StringBuildersequenceBuilder=newStringBuilder();
for(inti=0;i<str1.Length;i++)
{
for(intj=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];
intthisSubsBegin=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();
returnmaxlen;
}

The extra complexity in this method keeps the number of new String objects created to a minimum. This is important in C# because, since strings are immutable: every time a string field is assigned to, the old string sits in memory until the garbage collector runs. Therefore some effort was put into keeping the number of new strings low.

The algorithm might be simplified (left as an exercise to the reader) by tracking only the start position (in, say str1, or both str1 and str2) of the string, and leaving it to the caller to extract the string using this and the returned length. Such a variant may prove more useful, too, as the actual locations in the subject strings would be identified. 

#include"iostream"
usingnamespacestd;
char**A;
intmain(intargc,char*argv[])
{
intsatir,sira=1;
cin>>satir;
A=newchar*[satir];
for(inti=0;i<satir;i++)
*(A+i)=newchar[sira];
for(intj=1;j<=satir;j++)
cin>>A[0][j];
for(intj=1;j<=satir;j++)
cout<<A[0][j];
cin>>sira;
for(inti=1;i<=sira;i++)
cin>>A[i][0];
for(intj=1;j<=satir;j++)
cout<<A[0][j];
for(inti=1;i<=sira;i++){
for(intj=1;j<=satir;j++){
if(A[0][j]==A[i][0]){
cout<<A[i][0];
}
}
}
return0;
}

Python

[edit | edit source ]
deflongest_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]

Clojure

[edit | edit source ]
(defn lcs
[str1str2]
(loop [s1(seq str1),s2(seq str2),len0,maxlen0]
(cond
(>= maxlen(count s1))maxlen
(>= maxlen(+ (count s2)len))(recur(rest s1)(seq str2)0maxlen)
:else(let [a(nth s1len""),[b&s2]s2,len(inc len)]
(if (= ab)
(recurs1s2len(if (> lenmaxlen)lenmaxlen))
(recurs1s20maxlen))))))

Perl

[edit | edit source ]
sublc_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

formy$n1(1..$len1){
formy$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;
}

FunctionLongestCommonSubstring(S1AsString,S2AsString)AsString
MaxSubstrStart=1
MaxLenFound=0
Fori1=1ToLen(S1)
Fori2=1ToLen(S2)
X=0
Whilei1+X<=Len(S1)And_
i2+X<=Len(S2)And_
Mid(S1,i1+X,1)=Mid(S2,i2+X,1)
X=X+1
Wend
IfX>MaxLenFoundThen
MaxLenFound=X
MaxSubstrStart=i1
EndIf
Next
Next
LongestCommonSubstring=Mid(S1,MaxSubstrStart,MaxLenFound)
EndFunction

VB.NET

[edit | edit source ]
PublicFunctionLongestCommonSubstring(ByVals1AsString,ByVals2AsString)AsInteger
Dimnum(s1.Length-1,s2.Length-1)AsInteger'2D array
Dimletter1AsChar=Nothing
Dimletter2AsChar=Nothing
DimlenAsInteger=0
DimansAsInteger=0
ForiAsInteger=0Tos1.Length-1
ForjAsInteger=0Tos2.Length-1
letter1=s1.Chars(i)
letter2=s2.Chars(j)
IfNotletter1.Equals(letter2)Then
num(i,j)=0
Else
Ifi.Equals(0)Orj.Equals(0)Then
num(i,j)=1
Else
num(i,j)=1+num(i-1,j-1)
EndIf
Ifnum(i,j)>lenThen
len=num(i,j)
ans=num(i,j)
EndIf
EndIf
Nextj
Nexti
Returnans
EndFunction

COBOL

[edit | edit source ]

This algorithm uses no extra storage, but it runs in O(mnl) time. The 2 strings to compare should be placed in WS-TEXT1 and WS-TEXT2, and their lengths placed in WS-LEN1 and WS-LEN2, respectively. The output of this routine is MAX-LEN, the length of the largest common substring, WS-LOC1, the location within WS-TEXT1 where it starts, and WS-LOC2, the location within WS-TEXT2 where it starts. 

01 MAX-LENPIC 9999COMP.
01 WS-IX1PIC 9999COMP.
01 WS-IX2PIC 9999COMP.
01 WK-LENPIC 9999COMP.
01 WS-LOC1PIC 9999COMP.
01 WS-LOC2PIC 9999COMP.
01 WS-FLAGPIC X.
88 NO-DIFFERENCE-FOUNDVALUE 'N'.
88 DIFFERENCE-FOUNDVALUE 'Y'.

MOVEZEROTOMAX-LEN.
PERFORMVARYINGWS-IX1FROM1 BY1 UNTILWS-IX1>WS-LEN1
PERFORMVARYINGWS-IX2FROM1 BY1 UNTILWS-IX2>WS-LEN2
SETNO-DIFFERENCE-FOUNDTOTRUE
PERFORMVARYINGWK-LENFROMMAX-LENBY1 UNTIL 
WS-IX1+WK-LEN>WS-LEN1OR 
WS-IX2+WK-LEN>WS-LEN2OR
DIFFERENCE-FOUND
IFWS-TEXT1(WS-IX1:WK-LEN+1)=WS-TEXT2(WS-IX2:WK-LEN+1)
COMPUTEMAX-LEN=WK-LEN+1 
MOVEWS-IX1TOWS-LOC1
MOVEWS-IX2TOWS-LOC2
ELSE 
SETDIFFERENCE-FOUNDTOTRUE
END-IF 
END-PERFORM 
END-PERFORM 
END-PERFORM.

#include<string>
usingstd::string;
intLongestCommonSubstring(conststring&str1,conststring&str2)
{
if(str1.empty()||str2.empty())
{
return0;
}
int*curr=newint[str2.size()];
int*prev=newint[str2.size()];
int*swap=nullptr;
intmaxSubstr=0;
for(inti=0;i<str1.size();++i)
{
for(intj=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;
returnmaxSubstr;
}

Ruby

[edit | edit source ]
classString
defintersection(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.timesdo|x|
str.length.timesdo|y|
nextunlessself[x]==str[y]
matrix[x][y]=1+(([x,y].all?(&:zero?))?0:matrix[x-1][y-1])
nextunlessmatrix[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

Java

[edit | edit source ]
publicstaticintlongestSubstr(Stringfirst,Stringsecond){
intmaxLen=0;
intfl=first.length();
intsl=second.length();
int[][]table=newint[fl+1][sl+1];

for(inti=1;i<=fl;i++){
for(intj=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];
}
}
}
returnmaxLen;
}

- Java-Adaptation of C# code for retrieving the longest substring 

privatestaticStringlongestCommonSubstring(StringS1,StringS2)
{
intStart=0;
intMax=0;
for(inti=0;i<S1.length();i++)
{
for(intj=0;j<S2.length();j++)
{
intx=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;
}
}
}
returnS1.substring(Start,(Start+Max));
}

Java - O(n) storage

[edit | edit source ]
publicstaticintlongestSubstr(Strings,Stringt){
if(s.isEmpty()||t.isEmpty()){
return0;
}
intm=s.length();
intn=t.length();
intcost=0;
intmaxLen=0;
int[]p=newint[n];
int[]d=newint[n];
for(inti=0;i<m;++i){
for(intj=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;
}
returnmaxLen;
}

JavaScript

[edit | edit source ]
functionlongestCommonSubstring(string1,string2){
// init max value
varlongestCommonSubstring=0;
// init 2D array with 0
vartable=[],
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
vari,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;
}
}
}
returnlongestCommonSubstring;
}

Variant to return the longest common substring and offset along with the length 

functionlongestCommonSubstring(str1,str2){
if(!str1||!str2)
return{
length:0,
sequence:"",
offset:0
};

varsequence="",
str1Length=str1.length,
str2Length=str2.length,
num=newArray(str1Length),
maxlen=0,
lastSubsBegin=0;

for(vari=0;i<str1Length;i++){
varsubArray=newArray(str2Length);
for(varj=0;j<str2Length;j++)
subArray[j]=0;
num[i]=subArray;
}
varthisSubsBegin=null;
for(vari=0;i<str1Length;i++)
{
for(varj=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
};
}

TypeScript

[edit | edit source ]

Brute force as per other algorithms on this page, but storage is O(2n) as opposed to other implementations which require O(mn) storage 

exportfunctionlongestCommonSubstr(str1:string,str2:string){
if(!str1||!str2){return''}
conststr1Length=str1.length
conststr2Length=str2.length
letmaxLength=0
letbeginIndx=0// relative to str1
constnum=[newArray(str2Length),([]asnumber[]).fill(0,0,-str2Length)]as[number[],number[]]
for(leti=0;i<str1Length;++i){
constlastRow=1-i%2
constcurrentRow=num[1-lastRow]
for(letj=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
}
}
}
}
returnstr1.slice(beginIndx,maxLength+beginIndx)
}

Phix

[edit | edit source ]
functionlcs(stringa,b)
integerlongest=0
stringbest=""
fori=1tolength(a)do
integerch=a[i]
forj=1tolength(b)do
ifch=b[j]then
integern=1
whilei+n<=length(a)
andj+n<=length(b)
anda[i+n]=b[j+n]do
n+=1
endwhile
ifn>longestthen
longest=n
best=a[i..i+n-1]
endif
endif
endfor
endfor
returnbest
endfunction

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();
	
	// NOTE:
	// PHP is VERY inefficient at storing integers in a 2D array like this.
	// If the two strings are long, you run the risk of exhausting
	// all available memory.
	// For example, in PHP 7.4.9, this array was found to require 150 bytes per
	// stored integer.
	
	// 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)

Haskell

[edit | edit source ]
importData.List
importData.Function
lcstrxsys=maximumBy(compare`on`length).concat$[fxs'ys|xs'<-tailsxs]++[fxsys'|ys'<-drop1$tailsys]
wherefxsys=scanlg[]$zipxsys
gz(x,y)=ifx==ythenz++[x]else[]

Common Lisp

[edit | edit source ]
(defunlongest-common-substring(ab)
(let((L(make-array(list(lengtha)(lengthb)):initial-element0))
(z0)
(result'()))
(dotimes(i(lengtha))
(dotimes(j(lengthb))
(when(char=(charai)(charbj))
(setf(arefLij)
(if(or(zeropi)(zeropj))
1
(1+(arefL(1-i)(1-j)))))
(when(>(arefLij)z)
(setfz(arefLij)
result'()))
(when(=(arefLij)z)
(pushnew(subseqa(1+(-iz))(1+i))
result:test#'equal)))))
result))

Objective-C

[edit | edit source ]
+ (NSString*)longestCommonSubstring:(NSString*)substringstring:(NSString*)string{
if(substring==nil||substring.length==0||string==nil||string.length==0){
returnnil;

}
NSMutableDictionary*map=[NSMutableDictionarydictionary];
intmaxlen=0;
intlastSubsBegin=0;
NSMutableString*sequenceBuilder=[NSMutableStringstring];

for(inti=0;i<substring.length;i++)
{
for(intj=0;j<string.length;j++)
{
unicharsubstringC=[[substringlowercaseString]characterAtIndex:i];
unicharstringC=[[stringlowercaseString]characterAtIndex:j];
if(substringC!=stringC){
[mapsetObject:[NSNumbernumberWithInt:0]forKey:[NSStringstringWithFormat:@"%i%i",i,j]];
}
else{
if((i==0)||(j==0)){
[mapsetObject:[NSNumbernumberWithInt:1]forKey:[NSStringstringWithFormat:@"%i%i",i,j]];
}
else{
intprevVal=[[mapobjectForKey:[NSStringstringWithFormat:@"%i%i",i-1,j-1]]intValue];
[mapsetObject:[NSNumbernumberWithInt:1+prevVal]forKey:[NSStringstringWithFormat:@"%i%i",i,j]];
}
intcurrVal=[[mapobjectForKey:[NSStringstringWithFormat:@"%i%i",i,j]]intValue];
if(currVal>maxlen){
maxlen=currVal;
intthisSubsBegin=i-currVal+1;
if(lastSubsBegin==thisSubsBegin)
{//if the current LCS is the same as the last time this block ran
NSString*append=[NSStringstringWithFormat:@"%C",substringC];
[sequenceBuilderappendString:append];
}
else//this block resets the string builder if a different LCS is found
{
lastSubsBegin=thisSubsBegin;
NSString*resetStr=[substringsubstringWithRange:NSMakeRange(lastSubsBegin,(i+1)-lastSubsBegin)];
sequenceBuilder=[NSMutableStringstringWithFormat:@"%@",resetStr];
}
}
}
}
}
return[sequenceBuildercopy];
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int*lcommon(char*s,char*t){
intstrlen1=strlen(s);
intstrlen2=strlen(t);
intlen=(strlen1<strlen2)?strlen2:strlen1;
inti,j,k;
intlongest=0;
int**ptr=(int**)malloc(2*sizeof(int*));
staticint*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;
returnret;
}
intmain(intargc,char*argv[]){
inti,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);
}

proclcs{ab}{
setmaxLengthFound0
setmaxSubStart0
setla[stringlength$a]
setlb[stringlength$b]
for{seti0}{$i<$la}{incri}{
for{setj0}{$j<$lb}{incrj}{
for{setx0}{(($i+$x)<$la)&&(($j+$x)<$lb)&&([stringindex$a[expr$i+$x]]eq[stringindex$b[expr$j+$x]])}{incrx}{}
if{$x>$maxLengthFound}{
setmaxLengthFound$x
setmaxSubStart$i
# "we found $maxLengthFound common characters at position $maxSubStart"
}
}
}
return[stringrange$a$maxSubStart[expr$maxLengthFound+$maxSubStart-1]]
}


AltStyle によって変換されたページ (->オリジナル) /