调了半天TEL的代码！！最后杰sir 说 我的代码是n的3次，靠！！！我的半天时间啊！！！下面是TEL的代码。
1 #include <stdio.h> 2 #include <string.h> 3 #define N 1010 4 5 char str1[N],str2[N],str[N]; 6 int c[N][N],c1[N][N],len1,len2,len3; 7 int max (int x,int y) 8 { 9 return x>y?x:y; 10 } 11 void lcs (char str1[],char str2[],int end1,int end2) 12 { 13 int i,j; 14 memset(c,0,sizeof(c)); 15 for(i=1;i<=end1;i++) 16 { 17 for(j=1;j<=end2;j++) 18 { 19 if(str1[i]==str2[j]) 20 c[i][j]=c[i-1][j-1]+1; 21 else 22 c[i][j]=max(c[i-1][j],c[i][j-1]); 23 } 24 } 25 memset(c1,0,sizeof(c1)); 26 for(i=end1;i>=1;i--) 27 { 28 for(j=end2;j>=1;j--) 29 { 30 if(str1[i]==str2[j]) 31 c1[i][j]=c1[i+1][j+1]+1; 32 else 33 c1[i][j]=max(c1[i+1][j],c1[i][j+1]); 34 } 35 } 36 } 37 void Deal() 38 { 39 int kai1,kai2,jie1,jie2; 40 int n=len1;int m=len2; 41 int star=0;int ans=0,end; 42 int k1=1,k2=1; 43 //printf("%d ",len3); 44 for(int i=1;i<=n;i++) 45 { 46 if(str1[i]==str[k1]){star++;if(k1==1){kai1=i;}k1++;} 47 if(star==len3) 48 { 49 jie1=i;i=kai1;star=0;k1=1; 50 end=0;k2=1; 51 for(int j=1;j<=m;j++) 52 { 53 if(str2[j]==str[k2]) {end++;if(k2==1){kai2=j;}k2++;} 54 if(end==len3) 55 { 56 jie2=j;j=kai2;end=0;k2=1; 57 //printf(">>>-%d>>>>%d>>><<<<<%d<<<<<--%d ",kai1,jie1,kai2,jie2); 58 ans=max(ans,c[kai1-1][kai2-1]+c1[jie1+1][jie2+1]); 59 } 60 } 61 } 62 } 63 printf(" %d ",ans+len3); 64 } 65 int main () 66 { 67 int T,j,k; 68 while(scanf("%d",&T)!=EOF) 69 { 70 for(int i=1;i<=T;i++) 71 { 72 int max=0; 73 scanf("%s%s%s",str1+1,str2+1,str+1); 74 len1=strlen(str1+1); 75 len2=strlen(str2+1); 76 len3=strlen(str+1); 77 lcs(str1,str2,len1,len2); 78 printf("Case #%d:",i); 79 Deal(); 80 } 81 } 82 }
这是之前的ac代码！！我这是怎么了，擦，，ac了 还找虐啊
1 #include <stdio.h> 2 #include <string.h> 3 #define N 1010 4 5 char str1[N],str2[N],str[N]; 6 int c[N][N],c1[N][N],len1,len2,len3; 7 int sa[N][3],sb[N][3]; 8 int max (int x,int y) 9 { 10 return x>y?x:y; 11 } 12 void lcs (char str1[],char str2[],int end1,int end2) 13 { 14 int i,j; 15 memset(c,0,sizeof(c)); 16 for(i=1;i<=end1;i++) 17 { 18 for(j=1;j<=end2;j++) 19 { 20 if(str1[i]==str2[j]) 21 c[i][j]=c[i-1][j-1]+1; 22 else 23 { 24 if(c[i][j-1]>c[i-1][j]) 25 c[i][j]=c[i][j-1]; 26 else 27 c[i][j]=c[i-1][j]; 28 } 29 } 30 } 31 memset(c1,0,sizeof(c1)); 32 for(i=end1;i>=1;i--) 33 { 34 for(j=end2;j>=1;j--) 35 { 36 if(str1[i]==str2[j]) 37 c1[i][j]=c1[i+1][j+1]+1; 38 else 39 { 40 if(c1[i][j+1]>c1[i+1][j]) 41 c1[i][j]=c1[i][j+1]; 42 else 43 c1[i][j]=c1[i+1][j]; 44 } 45 } 46 } 47 } 48 void Deal() 49 { 50 int k,j,t1,t2; 51 t1=t2=0; 52 int n=len1;int m=len2; 53 for(int i=1;i<=n;i++) 54 if(str1[i]==str[1]) 55 { 56 for(j=i+1,k=1;j<=n;j++) 57 { 58 if(str1[j]==str[k+1]) k++; 59 if(k==len3) break; 60 } 61 if(k==len3) sa[t1][0]=i,sa[t1++][1]=j; 62 } 63 for(int i=1;i<=m;i++) 64 if(str2[i]==str[1]) 65 { 66 for(j=i+1,k=1;j<=m;j++) 67 { 68 if(str2[j]==str[k+1]) k++; 69 if(k==len3) break; 70 } 71 if(k==len3) sb[t2][0]=i,sb[t2++][1]=j; 72 } 73 int ans=0; 74 for(int i=0;i<t1;i++) 75 for(int j=0;j<t2;j++) 76 //printf(">>>-%d>>>>%d>>><<<<<%d<<<<<--%d ",sa[i][0],sa[i][1],sb[j][0],sb[j][1]); 77 ans=max(ans,c[sa[i][0]-1][sb[j][0]-1]+c1[sa[i][1]+1][sb[j][1]+1]); 78 printf(" %d ",len3+ans); 79 } 80 int main () 81 { 82 int T,j,k; 83 while(scanf("%d",&T)!=EOF) 84 { 85 for(int i=1;i<=T;i++) 86 { 87 int max=0; 88 scanf("%s%s%s",str1+1,str2+1,str+1); 89 len1=strlen(str1+1); 90 len2=strlen(str2+1); 91 len3=strlen(str+1); 92 lcs(str1,str2,len1,len2); 93 printf("Case #%d:",i); 94 Deal(); 95 } 96 } 97 }