0
Your rating: None
CodeChef submission 130857 (C) 

CodeChef submission 130857 (C) plaintext list. Status: WA, problem J2, contest NOV09. By rookie (rookie), 2009-11-11 13:20:17.
  1. #include<stdio.h>
  2. #include<string.h>
  3.  
  4. int L[1000][1000];
  5. int L1[1000][1000];
  6. int D[1000][1000];
  7.  
  8. int lcs_fun(char[],char[],int,int);
  9.  
  10. int main()
  11. {
  12. 	char s[1002],t[1002];
  13. 	int tc,index=0,m,n,i=0,j=0,l1=0,l2=0,x=0;
  14.  
  15. 	scanf("%d",&tc);
  16. 	while(index<tc)
  17. 	{
  18. 		scanf("%s",s);
  19. 		scanf("%s",t);
  20. 		m=strlen(s);n=strlen(t);
  21. 		
  22. 		for(i=0;i<m;i++)
  23. 		for(j=0;j<n;j++)
  24. 		{
  25. 			if(i==0 || j==0)
  26. 			L1[i][j]=0;
  27. 		
  28. 			else if(i>0 && j>0 && s[i]==t[j])	
  29. 			{
  30. 				L1[i][j]=L1[i-1][j-1]+1;
  31. 			}
  32. 			else
  33. 			{
  34. 				l1=L1[i-1][j];
  35. 				l2=L1[i][j-1];
  36. 		        	L1[i][j]=(l1>l2)?l1:l2;
  37. 			}	
  38. 			//printf("%d ",l1);
  39. 		}
  40. 			//if(L[m-1][n-1]==0)
  41. 			//printf("%d ",(L1[m-1][n-1]));
  42. 			//else
  43. 			printf("%d ",(1+L1[m-1][n-1]));
  44. 	
  45. 		
  46. 	/*	for(i=0;i<m;i++)
  47. 		{
  48. 			for(j=0;j<n;j++)
  49. 			{
  50. 				if(i==0 || j==0)
  51. 				L1[i][j]=0;
  52. 				else
  53. 				L1[i][j]=-1;
  54. 			}
  55. 		}
  56. 			  
  57. 		//printf("%d ",lcs_fun(s,t,m-1,n-1));	
  58. 		x=lcs_fun(s,t,m-1,n-1);
  59. 		if(x==0) printf("%d ",x);
  60. 		else
  61. 		printf("%d ",1+x);
  62. 	*/
  63.  
  64. 		for(j=0;j<n;j++)
  65. 		for(i=0;i<m;i++)
  66. 		{
  67. 			if(i==0 || j==0)
  68. 				D[i][j]=1;
  69. 			else
  70. 			{
  71. 				D[i][j]=0;
  72. 	
  73. 				if(s[i]==t[j])
  74. 					D[i][j]=D[i-1][j-1];
  75. 				else
  76. 				{
  77. 					if(L[i-1][j]==L[i][j])
  78. 					D[i][j]=D[i][j]+D[i-1][j];
  79. 					if(L[i][j-1]==L[i][j])
  80. 					D[i][j]=D[i][j]+D[i][j-1];
  81. 					if(L[i-1][j-1]==L[i][j])
  82. 					D[i][j]=D[i][j]-D[i-1][j-1];
  83. 				}
  84. 			}
  85. 			
  86.   		}
  87. 		//printf("i=%d,i=%d,%d ",i,j,D[i-1][j-1]);
  88. 		printf("%d ",(D[m-1][n-1])%23102009);
  89. 		printf("\n");
  90. 		
  91. 		/*for(i=0;i<m;i++)
  92. 		{
  93. 			for(j=0;j<n;j++)
  94. 			printf("%d ",L1[i][j]);
  95. 			printf("\n");
  96. 		}*/
  97. 	
  98. 		index++;
  99. 	}
  100. 	
  101. 	return 0;
  102. }
  103. /*
  104. int lcs_fun(char x[],char y[],int i,int j)
  105. {
  106. 	int l1,l2;
  107. 	
  108. 	if(L1[i][j]!=-1)
  109. 	return L1[i][j];	
  111. 	if(x[i]==y[j])
  112. 	{
  113. 		L1[i][j]= (lcs_fun(x,y,i-1,j-1)+1);
  114. 	}
  115. 	else
  116. 	{
  117. 		l1=lcs_fun(x,y,i-1,j-1);
  118. 		l2=lcs_fun(x,y,i,j-1);
  119. 	
  120. 		l1=((l1>l2)?l1:l2);
  121. 		L1[i][j]=l1;
  122. 		 
  123. 	//return (L1[i][j]);
  124. 	
  125. 	}
  126. 	return (L1[i][j]);
  127. }	
  128.  
  129. */
  130.  
  131. 	
  132.

Comments