河南省赛之Substring

 1 //就是字符串和它的逆串最大连续公共字串
 2 
 3 #include<stdio.h>
 4 #include<string.h>
 5 #include<stdlib.h>
 6 char a[100];
 7 char b[100];
 8 int c[100][100];
 9 
10 int main()
11 {
12     int n,i,j,k,t,p;
13     scanf("%d",&n);
14     while(n--)
15     {
16         scanf("%s",a);
17         t=strlen(a);
18         for(i=0;i<t;i++)
19             b[t-1-i]=a[i];
20         b[t]='\0';
21     //    strcpy(b,a);
22     //    strrev(b);
23         p=0;
24         memset(c,0,sizeof(c));
25         for(i=1;i<=t;i++)
26             for(j=1;j<=t;j++)
27             {
28                 if(a[i-1]==b[j-1])
29                     c[i][j]=c[i-1][j-1]+1;//因为是连续的，所以当a[i-1]！=b[j-1]不用更新其它的值
30             //    else
31             //        c[i][j]=c[i-1][j]>c[i][j-1]?c[i-1][j]:c[i][j-1];
32                 if(p<c[i][j])
33                 {
34                     p=c[i][j];
35                     k=i;
36                 }
37             }
38             for(i=k-p;i<k;i++)
39                 printf("%c",a[i]);
40             printf("\n");
41     }
42     return 0;
43 }