int to size_t warning
从上面KMP匹配代码引出的一个经典数据类型转换的问题。
int KMP(string str, string pat, int *next)
{
int i=0, j=0;
while(i<str.size() && j<pat.size())
{
if(j==-1 || str[i]==pat[j])
i++,j++;
else
j=next[j];
}
if(j==pat.size())
return i-j;
else
return -1;
}
这个代码看似没有问题，其实有个严重的问题，string.size() 返回的是size_t类型，这个string封装好的，实际也是长度必为正值，j=-1时，例如j=0, j=next[j] 之后j==-1，然后j<pat.size()
你猜结果如何？ 居然返回false了，然后退出循环了！！！！
结果是系统进行隐式转换，int->size_t, 然后-1二进制是32个1，然后变成无符号就是2^32-1,远大于pat.size()，于是bug了。。。
为啥系统的隐式转换是int->size_t(unsigned int)? 因为size_t范围全是非负数，从0开始最大值比int大得多，如果size_t->int的话，就像倒水一样，水比杯子容量还大，自然扑出来了。出现严重的溢出后果。
但其实int->size_t也是有验证问题，当int时负数，转的话就变成一个对应的无符号整数了。所以系统的设计，觉得size_t->int后果更严重，而int->size_t是程序员自己去控制的，因为即使前者强制转换也有可能是溢出的！
所以最好的方法就是要么非常清楚的系统的隐式转换规则，要么自己强制转换，不要寄希望于模棱两可的隐式转换。
Adhoc就是这样的，用long long的时候，给long long a赋值，LL a=0LL, 这样保证强制转换。
还有李沐MLSS talk里slide上的 稀疏矩阵里for的变量都是size_t类型的，因为下标永远都是非负数的。
正确KMP代码：
int KMP(string str, string pat, int *next)
{
int i=0, j=0;
while(i<(int)str.size() && j<(int)pat.size())
{
if(j==-1 || str[i]==pat[j])
i++,j++;
else
j=next[j];
}
if(j==pat.size())
return i-j;
else
return -1;
}