#H1028. 「MCOI-04」Dream and Strings

「MCOI-04」Dream and Strings

题目描述

Tommy 的加密系统用了如下的字符串哈希算法:

int Hash(std::string s, int base, int mod) {
  int result = 0;
  for(int i=0; i<s.length(); i++)
    result = (1ll * result * base + s[i]) % mod;
  return result;
}

其中 base\texttt{base}mod\texttt{mod} 是给定参数,满足 257basemod109+9257\le\texttt{base}\le\texttt{mod}\le10^9+9,并且 mod\texttt{mod} 是一个质数。

现在 Dream 要破解 Tommy 的密文,先需要找到一个适合的哈希碰撞。给定 base\texttt{base}mod\texttt{mod},和一个字符串 SS,请找一个一样长度的字符串 TT 使得 S=T|S|=|T|hash(S)=hash(T)\texttt{hash(S)=hash(T)},但是 SSTT 有至少一个位置不同。

如果有多个合法的 TT,输出任意一个即可。

输入格式

第一行,两个正整数 base\texttt{base}mod\texttt{mod}
第二行,一个由小写字母组成的字符串 SS

输出格式

一行,一个由小写字母组成的字符串 TT,表示答案。

257 997
aabdccbabdcdcadbcabcabaabdbbddbaabcadabcbcdacbbaac
lmzaeccihyailccmzzaxshssgbvjvhthllyofzudraatifnzxy

说明/提示

数据规模与约定

如果 SS 是一个字符串,S|S| 是它的长度。

对于前 10%10\% 的数据,mod=997\texttt{mod}=997
对于前 40%40\% 的数据,S=2×105|S|=2\times10^5 并且 SS 随机。
对于 100%100\% 的数据,50S2×10550\le|S|\le2\times10^5257base<mod109+9257\le\texttt{base}<\texttt{mod}\le10^9+9mod\texttt{mod} 是一个质数。

说明

Minecraft OI Round 4 D
idea & solution:w33z8kqrqk8zzzx33 check:MatKave