POI 2000 Repetitions 最长公共子串

这是一个经典的求多个串的最长公共子串的问题。如果设字符串的个数为N，每个串最大的长度为L，则这道题有时间复杂度为O(NL^4),O(NL^3),O(NL^2)和O(NL)的算法。

最简单的想法是对于某一个串，取出它的所有的L^2个子串，然后再在其他每一个字符串中进行朴素的匹配，很显然是O(NL^4)。如果生搬硬套地用KMP，那么是O(NL^3)的算法。仔细一想，其实枚举所有的L^2个子串是完全没有必要的，仅仅取出某一个串的L个后缀，对于每一个后缀在其他的所有串中部分匹配即可，用朴素匹配就是O(NL^3)，用KMP就是O(NL^2)，可以通过所有测试点。

另外，如果用Trie，把每个串的所有后缀全部插入Trie树中，标记每个节点所属的原串。找到最深的属于所有串的节点，它的最大深度就是最长公共前缀，时间复杂度依然是O(N*L^2)，但是会有一点超时。

对于这道题来说，对某个串的每个后缀进行部分模式匹配，O(NL^2)的算法就可以了。如果想进一步探究，恐怕就要用到后缀树了，广义后缀树求最长公共子串有O(NL)的算法，我还没有学过，现在正在苦读中。

下面是我的O(N*L^2)的KMP。

/* 
 * Problem: POI2000 pow
 * Author: Guo Jiabao
 * Time: 2009.1.5 13:53
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXL=2002;
const int MAXN=6;

int N,Ans,Max;
char S[MAXN][MAXL];
int Flee[MAXL];

void init()
{
	freopen("pow.in","r",stdin);
	freopen("pow.out","w",stdout);
	scanf("%d",&N);
	for (int i=1;i<=N;i++)
	{
		S[i][0]=1;
		scanf("%sn",S[i]+1);
	}
}

void KMP(char *A,char *B)
{
	int i,j,La,Lb;
	La=strlen(A+1);
	Lb=strlen(B+1);
	Flee[1]=0;
	for (j=0,i=2;i<=Lb;i++)
	{
		while (j>0 && B[j+1]!=B[i]) j=Flee[j];
		if (B[j+1]==B[i]) j++;
		Flee[i]=j;
	}
	for (j=0,i=1;i<=La;i++)
	{
		while (j>0 && B[j+1]!=A[i]) j=Flee[j];
		if (B[j+1]==A[i]) j++;
		if (j>Max)
			Max=j;
	}
}

void solve()
{
	int i,Min;
	char *s;
	for (s=S[1];*s;s++)
	{
		Min=2000;
		for (i=2;i<=N;i++)
		{
			Max=0;
			KMP(S[i],s);
			if (Max < Min)
				Min=Max;
		}
		if (Min>Ans)
			Ans=Min;
	}
}

int main()
{
	init();
	solve();
	printf("%d",Ans);
	return 0;
}

<h2><span class="mw-headline">最长公共子串 </span></h2>

给出几个由小写字母构成的单词，求它们最长的公共子串的长度。

任务

从文件中读入单词
计算最长公共子串的长度
输出结果到文件

输入

文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。

输出：

仅一行，一个整数，最长公共子串的长度。

样例输入：
```
3
  abcb
  bca
  acbc
```
样例输出：
```
2
```

上次修改时间 2017-02-03

相关日志