3098: Hash Killer II

Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge

Submit: 1555  Solved: 819

[Submit][Status][Discuss]

Description

(Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) (Ben Smith) Substring definitions are S[l], S[L + 1],… S[r] so continuous. Two strings are considered different if and only if the characters in one position are different.

VFleaKing thought this was a naked Hash question. So I decided to write hash + sort. The number of nodes in the length range represented by the suffix automatic machine contains L, the number of nodes in the depth of the suffix tree is L. But HZHWCMHF takes a look at VFleaKing’s approach and says it’s very sweaty. So he tried to cut him off.

VFleaKing uses a lexicographical hash, which looks like this: u64 val = 0; for (int i = 0; i < l; i++) val = (val * base + s[i] – ‘a’) % Mod; U64 is unsigned int64, the range is 0, 2^64. Base is a constant, VFleaKing determines its mood. Mod = 1000000007. Then VFleaKing sorts the hashes, deduplicates them, and finds out how many different hashes there are. The C++ code for its algorithm is as follows:

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 certainly knows how to jam! But he wants to test you. \

Input

No input. \

Output

You need to output a set of data to make the VFleaKing code WA out. We will use Special Judge to check the validity of your results. The first line contains two numbers, n and L, separated by Spaces. The second line is a string of length N. Contains only ‘a’ to ‘z’. Need to ensure that 1 <= n <= 10^5, 1 <= L <= n, do not conform to the above format will WA. Do not have redundant characters, which may cause you to WA.

Sample Input

There is no \

Sample Output

8 4 buaabuaa (of course this output will be WA) \

HINT

If there are 23 or more people in a room, there is a greater than 50% chance that at least two of them will share a birthday. \

Source

VFleaKing & hzhwcmhf

Title link: www.lydsy.com/JudgeOnline…

Analysis:

If there are 23 or more people in a room, there is a greater than 50% chance that at least two of them will share a birthday.

Birthday attack: If you randomly select n numbers, you can select the same number at most √n times (not considering Rp broken).

Again, this one has a Hash value between 0 and 1000000007. That’s about 10^5 times

The only thing to note is that l has to be large enough to have more options than Mod, otherwise it’s impossible for two numbers to have the same Hash

Here is the AC code:

1 #include<cstdio> 2 #include<cstdlib> 3 using namespace std; 4 int main() 5 { 6 int n=100000,l=20; 7 printf("%d %d\n",n,l); 8 for (int i=1; i<=n; i++) 9 printf("%c",(char)(rand()%26+'a')); 10 printf("\n"); 11 return 0; 12}Copy the code