Description:
Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

Input:
测试数据有若干行字符串，包括字母，数字，符号。（字母区分大小写）
 
Output:
与输入相对应每一行输出一个整数，代表最长有效密码串的长度。

Sample Input:
ABBA
12ABBA
A
ABAKK
51233214
abaaab
Sample Output:
4
4
1
3
6
5
 

又是后缀数组的题，直接套模板就是了

没有模板

我感兴趣

#include<stdio.h>
int datas(char a[],int j,int k)
{
 int i,n,m=0;
 n=((j+2)==k)?1:0;
 while(j>=0&&k<strlen(a))
   {
    if(a[j--]==a[k++])
      m+=2;
    else
      break;
   }
 return m+n;
}


void main()
{
   int i,k,m=0,n=0;
   char a[200];
   gets(a);
   if(strlen(a)>1)
    {
     for(i=0;i<strlen(a)-1;i++)
       {
    if(a[i]==a[i+1])
      n=datas(a,i,i+1);
    if(m<n)m=n;
       }
     for(i=0;i<strlen(a)-2;i++)
       {
    if(a[i]==a[i+2])
      n=datas(a,i,i+2);
    if(m<n)m=n;
       }
     }
   else if(strlen(a)==1)m=1;
  printf("%d\n\n",m);
  getch();
}


[ 本帖最后由 UserYuH 于 2009-9-19 01:40 编辑 ]

就算是DP也用不着三次方的复杂度

很长时间没写了，都荒废了。感觉现在自己在退步。写个代码练习一下吧，不要求 AC ，只是纯属练习一下：

#include<stdio.h>
#include<string.h>
#define N  100
int check(char *,char *);
int main(void)
{
    char ch[N];
    int num,tmp;
    int i,j,len;
    fgets(ch,N,stdin);
    num=1;
    len=strlen(ch)-1;
    for(i=0;i<len;++i)
    {
        for(j=len;j>i;--j)
        {
            if(ch[i]==ch[j])
            {
                tmp=check(&ch[i],&ch[j]);
                if(tmp>num)
                {
                    num=tmp;
                }
            }
        }
    }
    printf("%d\n",num);
}
int check(char *p,char *q)
{
    int n=q-p+1;
   
    while(p<q)
    {
        if(*p!=*q)
        {
            return 1;
        }
        p++;
        q--;
    }
   
    return n;
}

六楼的文件输入fgets行吗？？？

扩展KMP 或 后缀数组/树