F题 Substring（最大公共子串），f题substring

F题 Substring（最大公共子串），f题substring

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

题意：给一个字符串a,你找出字符串a的一个子串,把这个子串逆序后还是字符串a的子串。

解题思路：求字符串a和其逆序字符串b的最大公共子串。

子串：字符串s的子串[i:j](i<=j）表示s串中从i到j的一段连续的字符构成的字符串。

公共子串：字符串U 如果既是字符串S的子串又是字符串T的子串,则字符串U 是字符串S和T的一个公共子串。

最长公共子串:字符串S和T的最长公共子串是指字符串S和T的所有公共子串中长度最大的子串。

参考上的解题思路：http://blog.csdn.net/u012102306/article/details/53184446

此题借助一个二维数组标记相同的字符为1，不同的字符为0，对角线的和最大的即为所求的最大公共子串。

例如第一个测试数组：

a:ABCABA          b:ABACBA

标记图：（相同的字符为1，不同的字符为0，对角线的和最大的即为所求的最大公共子串）

	A	B	C	A	B	A
A	1	0	0	1	0	1
B	0	1	0	0	1	0
A	1	0	0	1	0	1
C	0	0	1	0	0	0
B	0	1	0	0	1	0
A	1	0	0	1	0	1

有图很清楚的可以看到黄色的对角线为最大公共子串，但是想要求每个对角线的和是很麻烦的，对此这个例子要求6*6个和。

怎样优化呢，这就要用到动态规划，转移方程式：

a[i][j]=1;i=0或者j=0;

a[i][j]=a[i-1][j-1]+1;

此时的标记图：

此时只要遍历一下dp数组就可以找到最大公共子串的长度以及此子串的最后一位坐标。

输出需要注意的是一种情况：

ABSDFBAA此时AB和AA长度相同,要输出AB.在这错了好几次。。

我的代码：

#include<bits/stdc++.h>
using namespace std;
char a[100],b[100];
int dp[100][100],len;
void LCS()
{
    int i,j,maxn=-1,x;
    memset(dp,0,sizeof(dp));
    for(i=0; i<len; i++)
        for(j=0; j<len; j++)
        {
            if(b[i]==a[j])
            {
                if(i==0||j==0)
                    dp[i][j]=1;
                else
                    dp[i][j]=dp[i-1][j-1]+1;
            }
            else
                dp[i][j]=0;
            if(maxn<=dp[i][j])
            {
                maxn=dp[i][j];
                x=i;
            }
        }
        for(i=x; i>=x-maxn+1; i--)//注意假如有相同的要先输出最右边的
            printf("%c",b[i]);
        cout<<endl;
}
int main()
{
    int num;
    scanf("%d",&num);
    while(num--)
    {
        int k=0,i;
        scanf("%s",a);
        len=strlen(a);
        for(i=len-1; i>=0; i--) //逆序串
        {
            b[k++]=a[i];
        }
        LCS();
    }
}