1238 substrings.cpp

来自「ACM 威士忌部分答案」· C++ 代码 · 共 53 行

//枚举，比较 
#include <cstdio>
#include <string>
using namespace std;
char text[101][101];
char inv[101][101];
char sub[5001][101];

int comp(const void*p1,const void*p2)
{
	return strlen((char*)p1)>=strlen((char*)p2);
}

int main()
{
	int i,j,l,k,n,t,lmax;
	
	scanf("%d",&t);
	while( t-- )
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%s",text[i]);
		memset(sub,0,sizeof(sub));
		
		lmax=0;k=0;
		qsort(text,n,sizeof(text[0]),comp);
		
		for(i=0;i<strlen(text[0]);i++)
			for(j=1;j<=strlen(text[0])-i;j++)
				strncpy(sub[k++],text[0]+i,j);

		for(l=1;l<n;l++)
		{
			for(i=strlen(text[l])-1,j=0;i>=0;i--)
				inv[l][j++]=text[l][i];
			inv[l][j]=0;
		}
		
		qsort(sub,k,sizeof(sub[0]),comp);
		for(i=k-1;i>=0;i--)
		{
			for(j=1;j<n;j++)
				if(strstr(text[j],sub[i])==NULL && strstr(inv[j],sub[i])==NULL)
					break;
			if(j==n && lmax<strlen(sub[i]))
				lmax=strlen(sub[i]);
		}
		printf("%d\n",lmax);
	}
	return 0;
}