企业宣传注册哪些论坛 网站好,wordpress 结构分析,网站建设与运营及营销服务,搜狐快站官网Description 这天天气不错#xff0c;hzhwcmhf神犇给VFleaKing出了一道题#xff1a;给你一个长度为N的字符串S#xff0c;求有多少个不同的长度为L的子串。子串的定义是S[l]、S[l 1]、... S[r]这样连续的一段。两个字符串被认为是不同的当且仅当某个位置上的字符不同。 VF…Description 这天天气不错hzhwcmhf神犇给VFleaKing出了一道题给你一个长度为N的字符串S求有多少个不同的长度为L的子串。子串的定义是S[l]、S[l 1]、... S[r]这样连续的一段。两个字符串被认为是不同的当且仅当某个位置上的字符不同。 VFleaKing一看觉得这不是Hash的裸题么于是果断写了哈希 排序。而hzhwcmhf神犇心里自然知道这题就是后缀数组的height中 L的个数 1就是后缀自动机上代表的长度区间包含L的结点个数就是后缀树深度为L的结点的数量。但是hzhwcmhf神犇看了看VFleaKing的做法表示非常汗。于是想卡掉他。 VFleaKing使用的是字典序哈希其代码大致如下u64 val 0;for (int i 0; i l; i) val (val * base s[i] - a) % Mod;u64是无符号int64范围是[0, 2^64)。base是一个常量VFleaKing会根据心情决定其值。Mod等于1000000007。VFleaKing还求出来了base ^ l % Mod即base的l次方除以Mod的余数这样就能方便地求出所有长度为L的子串的哈希值。然后VFleaKing给哈希值排序去重求出有多少个不同的哈希值把这个数作为结果。其算法的C代码如下 typedef unsigned long long u64; const int MaxN 100000; inline int hash_handle(const char *s, const int n, const int l, const int base){ const int Mod 1000000007; u64 hash_pow_l 1; for (int i 1; i l; i) hash_pow_l (hash_pow_l * base) % Mod; int li_n 0; static int li[MaxN]; u64 val 0; for (int i 0; i l; i) val (val * base s[i] - a) % Mod; li[li_n] val; for (int i l; i n; i) { val (val * base s[i] - a) % Mod; val (val Mod - ((s[i - l] - a) * hash_pow_l) % Mod) % Mod; li[li_n] val; } sort(li, li li_n); li_n unique(li, li li_n) - li; return li_n;} hzhwcmhf当然知道怎么卡啦但是他想考考你。 Input 没有输入。 Output 你需要输出一组数据使得VFleaKing的代码WA掉。我们会使用Special Judge检查你的结果的正确性。第一行两个用空格隔开的数n、l。第二行是一个长度为n的字符串。只能包含a~z。需要保证1 n 10^5, 1 l n不符合以上格式会WA。不要有多余字符很可能导致你WA。 Sample Input 没有 Sample Output 8 4 buaabuaa 当然这个输出是会WA的 HINT 如果一个房间里有23个或23个以上的人那么至少有两个人的生日相同的概率要大于50%。 生日悖论 这里取模的数是10^97,所以只需要生成sqrt10^97≈100000的数就会出现冲突 1 #includecstdio
2 #includecstdlib
3 int main(){
4 printf(100000 20\n);
5 for(int i1;i100000;i) printf(%c,(rand()%26a));
6 printf(\n);
7 } 转载于:https://www.cnblogs.com/wuminyan/p/5211715.html
