1066.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1066 on 2006-01-07 at 01:20:16 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 128;

char word[MAX][MAX];

bool find(const char*, const char*);
int n;

int main()
{
	char str1[MAX], str2[MAX];
	int t, T, i, j;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d\n", &n);
		int m = MAX, ln;
		for(i = 0; i < n; i++) {
			int k = strlen(gets(word[i]));
			if(k < m) m = k, ln = i;
		}
		int l = 0, h = m;
		while(l != h) {
			int mid = (l + h + 1) / 2;
			bool have = false;
			for(i = 0; i < m; i++) {
				if(m-i >= mid) {
					str1[mid] = str2[mid] = 0;
					for(j = i; j < i+mid; j++) {
						str1[j-i] = word[ln][j];
						str2[j-i] = word[ln][2*i+mid-1-j];
					}
					if(find(str1, str2)) { have = true; break; };
				}
			}
			if(have) l = mid;
			else h = mid - 1;
		}
		printf("%d\n", h);
	}
	
	
	return 0;
}

bool find(const char* str1, const char* str2)
{
	int i;
	for(i = 0; i < n; i++) {
		if(strstr(word[i], str1) == NULL && strstr(word[i], str2) == NULL) return false;
	}
	return true;
}