首页 > 代码库 > hdu 1238 Substrings

hdu 1238 Substrings

2024-07-16 22:03:57   225人阅读

Substrings

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7261    Accepted Submission(s): 3277


Problem Description
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.
 

Input
The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string. 
 

Output
There should be one line per test case containing the length of the largest string found.
 

Sample Input
2
3
ABCD
BCDFF
BRCD
2
rose
orchid
 

Sample Output
2
2

算法解析：

在多个字符串中寻找最长字串，并输出该字串的长度。首先找出最短的一个字符串，以最短字符串的所有子串从长到短搜索所有字符串，若全部满足存在某个最短字符串的子串或反转子串，输出该子串的长度。

需要利用的字符串函数

strlen：计算字符串的长度
strncpy：复制字符串的子串
strcpy：复制字符串
strstr：在字符串中寻找子字符串
strrev：对字符串进行反序

代码如下：

#include<stdio.h>
#include<string.h>
char str[100][101];
int n;
int searchMaxSubString(char *source)
{
	int i, j, subStrLen,sourceStrLen;
		int foundMaxSubStr;
	char subStr[101], revSubStr[101];
	subStrLen= sourceStrLen=strlen(source) ;
	while ( subStrLen > 0 )
	{                                                                    //搜索不同长度的子串，从最长的子串开始搜索
		for (i = 0; i <= sourceStrLen - subStrLen; i++) 
		{                                                                //搜索长度为subStrLen 的全部子串，共 sourceStrLen – subStrLen个
			                                                             //取source字符串中第i个字符开始的长度为subStrLend的子串
			strncpy(subStr, source+i, subStrLen);
			strncpy(revSubStr, source+i, subStrLen);
			subStr[subStrLen] = revSubStr[subStrLen] = '\0';
			strrev(revSubStr);                                           //得到反序子串
			foundMaxSubStr = 1;
			for( j = 0; j < n; j++)
				if ( strstr(str[j], subStr) == NULL && 
					strstr(str[j], revSubStr) == NULL ) 
				{
					foundMaxSubStr = 0;
					break;
				}
				if (foundMaxSubStr)
					return(subStrLen);
		}
		subStrLen--;
	}
	return 0;
}
int main()
{
	int N,min,a,x,i;
	scanf("%d",&N);
	while(N--)
	{
		scanf("%d",&n);
		min=100,i=0;
		while(i<n)
		{
			scanf("%s",str[i]);
			a=strlen(str[i]);
			if(min>a)
			{
				min=a;x=i;
			}
			i++;
		}
		printf("%d\n",searchMaxSubString(str[x]));
	}	
	return 0;
}


联系
我们