A Solution of A Written Question in An Examination (3)

Posted on

Question

假设以定长存储结构表示串，试设计一个算法，求串s和串t的一个最长公共子串。

Solution

串的定长存储表示可描述如下：

1
2
#define		MAXSTRLEN		255				//用户可在255以内定义最大串长
typedef		unsigned char	SString[MAXSTRLEN + 1];		//0号单元存放串的长度

对于求两个串s和t的公共子串，根据算法的空间复杂度分为两类：

  • (1) 空间复杂度为O(length(s) + length(t))
  • (2) 空间复杂度为O(length(s) * length(t))

对于第1种方法，可以采用串的模式匹配算法，对串s的每一个子串寻找其在串t中是否可以匹配。下面主要介绍第二种方法的一种实现。

考虑到串s和串t为定长存储结构，可以比较方便地建立二维数组A来表示两个串中每一个字符的匹配情况，如果s[i]和t[j]相等，则置A[i][j]>0，否则A[i][j]=0。因此，对于s和t的公共子串r，必有：

A[i][j] > 0, for continious s[i] and t[j] in r

为便于计算最长的r，特别地，置

A[i][j] = A[i - 1][j - 1] + 1, if s[i] == t[j]

此时A[i][j]表示对应的公共子串的长度。

因此，遍历A取A[i][j]的最大值，对应的子串即为所求的最长公共子串。

算法的C语言实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void lngstCmnSubStr(SString s, SString t, SString& r)
//求以定长存储表示的串s和t的最长公共子串，存入r
{
	r[0] = 0;
    int** ch = new int [s[0] + 1][t[0] + 1];
    
    for(int i = 1; i < s[0]; i++)
    {
    	for(int j = 1; j < t[0]; j++)
        {
        	if(s[i] != t[j])
            {
            	ch[i][j] = 0;
            } // if
            else
            {
            	if(j == 1 || i == 1)
                {
                	ch[i][j] = 1;
                }
                else
                {
                	ch[i][j] = ch[i - 1][j - 1] + 1;
                }
                // Refresh maxLen
                if(ch[i][j] > maxLen)
                {
                	maxLen = ch[i][j];
                    max_s = i;
                }
            } // else
        } // for
    } // for
    
    // Refresh r
    r[0] = maxLen;
    for(int i = 1; i < maxLen; i++)
    {
    	r[i] = s[max_s - maxLen + i];
    }
    
    delete ch[][];
} // lngstCmnSubStr()