首页 > 代码库 > POJ 1458 LCS 数组过小因编译器不同引发

POJ 1458 LCS 数组过小因编译器不同引发

按道理说LCS的问题应该讨论的很明白了,不应该出问题。昨天晚上手贱点开了暑期写的LCS滚动数组的代码。发现毫无逻辑错误。

但却是WA,用的C++,。于是随手换了个g++ 却手动把1-flag 与flag相比较输出最大,就AC

#include<stdio.h>
#include <math.h>
#include <string.h>
#define N 2000
char str1[N];
char str2[N];
int  dp[2][N];
int main()
{
   int i,j,n,m,flag;
   while(scanf("%s %s",str1,str2)!=EOF)
   {
	   memset(dp,0,sizeof(dp));
	   flag=1;
	   for(i=1;i<=strlen(str1);i++)
	   {
		   
		   for(j=1;j<=strlen(str2);j++)
		   {
			   if(str1[i-1] == str2[j-1])
				   dp[flag][j]=dp[1-flag][j-1]+1;
			   else if(dp[flag][j-1]>dp[1-flag][j])
				   dp[flag][j]=dp[flag][j-1];
			   else
				   dp[flag][j]=dp[1-flag][j];
		   }
		   flag=1-flag;
	   }
	   printf("%d\n",dp[1-flag][j-1]);
          
   }
   return 0;
}
没想到是编译器的问题,依旧在纠结我的程序逻辑哪里有问题。使用了好几个方法去测试。

在这期间问了好多人,发现大家都是一个写的模板,很少思考各种不同之间的问题,包括一个大神。。。。。。总是用已经可以成功的方法套。都说这样写没错别想那个了。

1. 测试数据弄多点,每次输出两者,看什么情况下最优。//结果总是1-flag最优,说明这种思路没错。

2. 逆向分析,既然是最后两者判断输出最优,那么必然是两个数组中j-1这个位置的问题,那肯定是最后一个字符匹配成功才导致的(不成功就是复制flag的了)

    但这逻辑上也是不同。。。。。

3. 在lj同学测试下,发现g++可以过

原来是数组开小了。。。。。。。。我擦,调了一晚上竟然这种结果,你要是re的话不早就好了???

C/C++不对内存越界检测,所以程序稀里糊涂越界,没被检测到。且g++ c++处理机制不同才导致。。。。

这个收获才是真多,,,,,,,

POJ 1458 LCS 数组过小因编译器不同引发