原文链接:http://imlazy.ycool.com/post.1861423.html
如果所有字符串的长度之和是L,则下面介绍的这个算法的平均效率O(L * logL),但是最坏情况下可能会再乘以O(l),l是每个字符串的平均长度。
首先对于每个字符串,取出以每个字符开头,到字符串尾的子串。比如字符串“acb”,从中取出的子串有“acb”、“cb”和“b”。如果所有字符串的总长度为L,则总共就有L个子串。我们把这些子串存在一个名为sub的数组中。(注意,最好用C风格的字符,这样可以直接引用每个子串的首地址,不用把这些子串另外转存。)
接下来就是主要花时间的步骤:把这L个子串排序。如果用快速排序的话时间就是O(L * logL)。比如共有三个字符串“acb”、“cbb”和“dcba”,从它们中取出的子串有:“acb”、“cb”、“b”、“cbb”、“bb”、“b”、“dcba”、“cba”、“ba”和“a”。把它们排序后的结果如下(为了看得清楚,我把字符串坚着放):
sub: 0 1 2 3 4 5 6 7 8 9
a a b b b b c c c d
c a b b b b c
b a b b
a |
但是这里有个问题,这个排序中的每次比较都是字符串的比较,它们会不会花很多时间呢。其实比较两个字符串的时间取决于它们开头有几个字符是相同的,如果相同的少,则很快就可以比完了。假设字符串的每个字符都是26个英文字母之一,则两个字符串开头有1个字符相同的概率是1 / 26,有2个字符相同的概率是1 / 262;学过概率论就知道,这样两个字符串开头相同的字符数的期望值为1 / 26 + 2 / 262 + 3 / 263 ... < 1。也就是说比较两个字符串的平均时间是常数极的。
但以上说的只是平均情况。在最最极端的情况下(虽然概率上不几乎不可能出现,但是出题的人一定会出这种极限数据),可能所有字符串都只含有同样的字符(比如要你求“aaaa”、“aaaa”和“aaaa”和最大公共子串),那么在排序算法中比较每两个子串时,都至少要把其中一个子串从头读到尾,时间数量级大约就是所有字符串的平均长度,也就是本文一开始说的,间时复杂度会上升到O(l * L * logL)。
把所有子串排好了序,就离答案很近了。不难想象,我们要求的最大公共子串一定是数组sub中相邻的几项的最大公共前缀。比如在上面的例子中,最大公共子串是“cb”,它就是数组sub中下标6、7和8这三项的最大公共前缀。
其实数组sub中需要存放的不只是每个子串的首地址,还需要存放每个子串属于第几个原字符串(在上面的例子中用颜色来表示),这在最后一个步骤中需要用到。
下面是最后的寻找步骤:在数组sub中,对于每一段相邻的且覆盖了所有原字符串的元素(而且只要最小段,也就是去掉该段的首、尾任意一个元素,它就不能覆盖所有原字符串了),求出该段首尾两个元素的最大公共前缀,即找到了所有原字符串的一个公共子串。枚举所有符合要求的段,就可以找出所有原字符串的最大公共子串。在前面的例子中,符合要求的段有[0,2]、[2,4]、[3,5]、[4,6]、[5,7]和[6,8],经过比较,在[6,8]这一段就找到了我们要求的最大公共子串“cb”。
这一步骤所花的时间是O(L),具体流程虽然不难,但是用文字说起来有点麻烦,所以还是详见后面的代码吧。可见这一步花的时间比起总的O(L * logL)算不了什么。
到这里算是讲完了。在UVA 11107有一个类似的问题,虽然有点不一样,但是道理是完全一样的。为了弥补我上面没有讲清楚的最后一个步骤,下面附上我这题的代码。
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAX_LEN = 1004;//Notice, the test data is wrong.
//The bound is 1004 but not 1000.
const int MAX_STR = 100;
struct SubStr {
const char* addr;
int num;
};
char g_str[MAX_STR][MAX_LEN + 1];
int g_strCnt;
SubStr g_subStr[MAX_STR * MAX_LEN];
int g_subStrCnt;
int subStrCmp(const void* a, const void* b) {
return strcmp(((const SubStr*)a)->addr, ((const SubStr*)b)->addr);
}
int commonLen(const SubStr& a, const SubStr& b) {
const char* i = a.addr;
const char* j = b.addr;
int len = 0;
while (*i && *j && *i == *j) {
len++;
i++;
j++;
}
return len;
}
void printStr(const char* str, int len) {
for (int i = 0; i < len; i++) {
printf("%c", *str);
str++;
}
printf("\n");
}
void initSubStr() {
g_subStrCnt = 0;
for (int i = 0; i < g_strCnt; i++) {
for (const char* j = g_str[i]; *j; j++) {
g_subStr[g_subStrCnt].addr = j;
g_subStr[g_subStrCnt].num = i;
g_subStrCnt++;
}
}
qsort(g_subStr, g_subStrCnt, sizeof(SubStr), subStrCmp);
}
int findLongest() {
int longest = 0;
SubStr* head = g_subStr;
SubStr* tail = g_subStr;
const SubStr* end = g_subStr + g_subStrCnt;
int half = g_strCnt / 2;
int coverCnt = 0;
int cover[MAX_STR];
memset(cover, 0, sizeof(cover));
while (head != end) {
//To find every pair of head and tail,
//that in the range [tail, head] there are exactly half + 1
//strings are covered.
while (coverCnt <= half && head != end) {
if (cover[head->num] == 0) {
coverCnt++;
}
cover[head->num]++;
head++;
}
while (coverCnt > half) {
cover[tail->num]--;
if (cover[tail->num] == 0) {
coverCnt--;
}
tail++;
}
if (coverCnt == half) {
int len = commonLen(*(tail - 1), *(head - 1));
if (len > longest) {
longest = len;
}
}
}
return longest;
}
//The work flow of this function is just like "findLongest()".
void printCommon(int longest) {
const SubStr* head = g_subStr;
const SubStr* tail = g_subStr;
const SubStr* pre = NULL;
const SubStr* const end = g_subStr + g_subStrCnt;
int half = g_strCnt / 2;
int coverCnt = 0;
int cover[MAX_STR];
memset(cover, 0, sizeof(cover));
while (head != end) {
while (coverCnt <= half && head != end) {
if (cover[head->num] == 0) {
coverCnt++;
}
cover[head->num]++;
head++;
}
while (coverCnt > half) {
cover[tail->num]--;
if (cover[tail->num] == 0) {
coverCnt--;
}
tail++;
}
if (coverCnt == half) {
int len = commonLen(*(tail - 1), *(head - 1));
if (len == longest
&& (pre == NULL
|| commonLen(*(tail - 1), *pre) < longest
)
) {
printStr((tail - 1)->addr, longest);
pre = tail - 1;
}
}
}
}
bool input() {
bool hasNext = false;
scanf("%d", &g_strCnt);
if (g_strCnt > 0) {
hasNext = true;
for (int i = 0; i < g_strCnt; i++) {
scanf("%s", g_str[i]);
}
}
return hasNext;
}
void solve() {
initSubStr();
int len = findLongest();
if (len == 0) {
printf("?\n");
}
else {
printCommon(len);
}
}
int main() {
int cnt = 0;
while (input()) {
if (cnt > 0) {
printf("\n");
}
solve();
cnt++;
}
return 0;
} |