以前在《编程珠玑》上看过后缀数组的作用,不过那道题的是针对单个字符串求最大重复连续子串的,而这道题是要求两个字符串的最长公共连续子串。一段时间内并不能把书上的那个解法应用到这道题上来。不过昨天晚上一是顿悟,加个标志位就行了嘛!
今天来试验了一下,果然AC。哈哈!
关于后缀数组的知识大家可以上网上搜或看《编程珠玑》上的那个例子。我这里给出这道题的AC代码,和大家分享。总体思路还是《编程珠玑》上的。另外,暴力枚举肯定也是能够求解这道题的,但是,效率是个问题。
这道题的URL:http://acm.hdu.edu.cn/showproblem.php?pid=1403
#include<iostream>
#include<string.h>
using namespace std;
const int Max = 100000 + 10;
char a[Max];
char b[Max];
struct Node
{
char *suf;
bool flag;
};
Node suffix[Max * 2];
int com(const void * a, const void *b)
{
return strcmp(((Node *)a)->suf, ((Node *)b)->suf);
}
int comLen(char *a, char *b)
{
int len = 0;
while(*a++ == *b++) len ++;
return len;
}
int main()
{
int max;
while(scanf("%s %s", a, b) != EOF)
{
int lenA = strlen(a);
int lenB = strlen(b);
for(int i=0; i<lenA; i++) suffix[i].suf = a+i, suffix[i].flag = false;
for(int i=0; i<lenB; i++) suffix[i+lenA].suf = b+i, suffix[i+lenA].flag = true;
qsort(suffix, lenA+lenB, sizeof(Node), com);
max = 0;
int temp;
for(int i=0; i<lenA+lenB-1; i++)
if((suffix[i].flag != suffix[i+1].flag) && (temp = comLen(suffix[i].suf, suffix[i+1].suf)) > max)
max = temp;
printf("%d\n", max);
}
system("pause");
return 0;
}