CF335B

 1 /*CF335B 
 2 这个题目的n达到50000，但是串只是有小写字母组成,所以如果字符串的长度大于2600，那么
 3 肯定存在，所开始输入就判断如果长度大于2600，那么直接找当个字母输出100个
 4 否则执行LCS模块，然后判断所得最长公共是否大于100，如果小于100，那么直接输出最长公共
 5 否则从两头分别取50个输出*/
 6 #include<stdio.h>
 7 #include<string.h>
 8 int dp[2600][2600],dir[2600][2600];
 9 char a[50005],b[2605],c[2605];
10 void LCS(int n,int m)
11 {
12     int i,j;
13     memset(dp,0,sizeof(dp));
14     memset(dir,0,sizeof(dir));
15     for(i=1;i<=n;i++)
16     for(j=1;j<=m;j++)
17         {
18             if(a[i-1]==b[j-1])
19             {
20                 dp[i][j]=dp[i-1][j-1]+1;
21                 dir[i][j]=1;
22             }
23             else if(dp[i-1][j]>dp[i][j-1])
24             {
25                 dp[i][j]=dp[i-1][j];
26                 dir[i][j]=0;
27             }
28             else 
29             {
30                  dp[i][j]=dp[i][j-1];
31                 dir[i][j]=2;
32             }
33     }
34 }
35 int cont=0;
36 void print(int n,int m)
37 {
38     if(n==0 || m==0) return;
39     if(dir[n][m]==1)
40     {
41         print(n-1,m-1);
42         c[cont++]=a[n-1];
43     }
44     else if(dir[n][m]==0) print(n-1,m);
45     else print(n,m-1);
46 }
47 int main()
48 {
49     int j,n;
50       int hash[250],flag=0,i=0;
51         char s;
52       memset(hash,0,sizeof(hash));
53      gets(a);
54      n=strlen(a);
55         for(i=0;i<n;i++)
56         {
57            hash[a[i]]++;
58         }
59         for(i=0;i<26;i++)
60         {
61             if(hash['a'+i]>=100) { s='a'+i; flag=1; break;}
62         }
63         if(flag) 
64         {
65             for(i=1;i<=100;i++)
66                 printf("%c",s);
67             printf("
");
68         }
69         else
70         {
71             for(i=0,j=n-1;i<n;i++,j--)
72                 b[j]=a[i];
73             cont=0;
74             memset(c,0,sizeof(c));
75             LCS(n,n);
76             print(n,n);
77             int num=strlen(c);
78             //printf("%d
",num);
79             char m1[51],m2[51];
80             if(num<=100) printf("%s
",c);
81             else
82             {
83                 memset(m1,0,sizeof(m1));
84                  memset(m2,0,sizeof(m2));
85                 for(i=0;i<50;i++)
86                     m1[i]=c[i];
87                 for(i=num-1,j=49;i>=num-50;i--,j--)
88                     m2[j]=c[i];
89                 //int num1=strlen(m1);
90                 //int num2=strlen(m2);
91                 printf("%s%s
",m1,m2);
92             }
93 
94     }
95     return 0;
96 }