NYOJ 308 Substring，nyoj308substring

NYOJ 308 Substring，nyoj308substring



Substring

时间限制：1000 ms  |  内存限制：65535 KB 难度：1

描述

You are given a string input. You are to find the longest substring of input such that the reversal of the substring is also a substring of input. In case of a tie, return the string that occurs earliest in input. 

Note well: The substring and its reversal may overlap partially or completely. The entire original string is itself a valid substring . The best we can do is find a one character substring, so we implement the tie-breaker rule of taking the earliest one first.

输入

The first line of input gives a single integer, 1 ≤ N ≤ 10, the number of test cases. Then follow, for each test case, a line containing between 1 and 50 characters, inclusive. Each character of input will be an uppercase letter ('A'-'Z').

输出

Output for each test case the longest substring of input such that the reversal of the substring is also a substring of input

样例输入

3                   
ABCABA
XYZ
XCVCX

样例输出

ABA
X
XCVCX

来源

第四届河南省程序设计大赛

上传者

张云聪

题意：求已知字符串与它的逆序字符串的最长公共连续字串。

思路：分别用一个数组存储字符串以及它的逆序字符串，然后两层循环就可以套公式了，当s1[i] = s2[j]时，dp[i+1][j+1] = dp[i][j]+1。然后记录并更新最大的字串长度以及到哪里结束，方便最后输出。

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
	int n;
//	scanf("%d",&n);
	cin >> n; 
//	getchar();
	while(n--)
	{
		int dp[55][55];
		memset(dp,0,sizeof(dp));
		char s1[55],s2[55];
		cin >> s1;
		int len = strlen(s1),k = len - 1;
		for(int i = 0;i < len && k >= 0;i++)
			s2[i] = s1[k--];
		s2[len] = '\0';    //注意这里 
		int maxn = 0;  //记录最长的公共串的长度 
		for(int i = 0;i < len;i++)
			for(int j = 0;j < len;j++)
			{
				if(s1[i] == s2[j])
					dp[i + 1][j + 1] = dp[i][j] + 1;
				if(dp[i + 1][j + 1] > maxn)  
				{
					maxn = dp[i + 1][j + 1];  // 更新长度 
					k = i;       //记录结束位置的下标 
				}
			}
		for(int i = k - maxn + 1;i <= k;i++)
			printf("%c",s1[i]);
		printf("\n");
	}
	return 0;
}