Beyond the Void
BYVoid
POI 2000 Repetitions 最長公共子串
本文正體字版由OpenCC轉換

這是一個經典的求多個串的最長公共子串的問題。如果設字符串的個數爲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

相關日誌