u64 val =0;for(int i =0; i < l; i++)
val = val * base + s[i]-'a';
u64 是无符号 int64,范围是 。VFleaKing 让 val 自然溢出。
base 是一个常量,VFleaKing 会根据心情决定其值。
VFleaKing 还求出来了 base ^ l,即 的 次方,这样就能方便地求出所有长度为 的子串的哈希值。
然后 VFleaKing 给哈希值排序,去重,求出有多少个不同的哈希值,把这个数作为结果。
其算法的 C++ 代码如下:
typedefunsignedlonglongu64;constint MaxN =100000;inlineinthash_handle(constchar*s,constint&n,constint&l,constint&base){
u64 hash_pow_l =1;for(int i =1; i <= l; i++)
hash_pow_l *= base;int li_n =0;static u64 li[MaxN];
u64 val =0;for(int i =0; i < l; i++)
val = val * base + s[i]-'a';
li[li_n++]= val;for(int i = l; i < n; i++){
val = val * base + s[i]-'a';
val -=(s[i - l]-'a')* hash_pow_l;
li[li_n++]= val;}sort(li, li + li_n);
li_n =unique(li, li + li_n)- li;return li_n;}
hzhwcmhf 当然知道怎么卡啦!但是他想考考你。
输出格式
你需要输出一组数据使得 VFleaKing 的代码 WA 掉。我们会使用 Special Judge 检查你的结果的正确性。