编码-百度之星资格赛Problem A-2016.05.14
Problem A
Accepts: 1014 Submissions: 8167
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
度熊手上有一本字典存储了大量的单词，有一次，他把所有单词组成了一个很长很长的字符串。现在麻烦来了，他忘记了原来的字符串都是什么，神奇的是他竟然记得原来那些字符串的哈希值。一个字符串的哈希值，由以下公式计算得到：
请帮助度熊计算大字符串中任意一段的哈希值是多少。
Input
多组测试数据，每组测试数据第一行是一个正整数NN，代表询问的次数，第二行一个字符串，代表题目中的大字符串，接下来NN行，每行包含两个正整数aa和bb，代表询问的起始位置以及终止位置。
Output
对于每一个询问，输出一个整数值，代表大字符串从 aa 位到 bb 位的子串的哈希值。
Sample Input
2
ACMlove2015
1 11
8 10
1
testMessage
1 1
Sample Output
6891
9240
88
我的代码：
include
include
//# include
using namespace std;
int main() {
//clock_t begin, end;
//srand((unsigned)time(NULL));
int N;int result = 0;while (cin >> N) { //begin = clock(); string s; cin >> s; int slen = s.length(); int t[100000]; for (int i = 0;i > a >> b) { if ((a slen) || (b slen)) { if(result) cout b) { int t = a; a = b; b = t; } int H = 1; for (int j = a - 1;j =9973) H = H % 9973; } result = H; cout 超时：TLE
请问各位大神哪里可以优化？
优化：
以下代码来自csdn“exmy”的博客
include
include
include
include
using namespace std;
const int maxn = 100000 + 10;
const int mod = 9973;
int n, a, b;
char s[maxn];
int dp[maxn];
int inv(int x, int y)
{
if(x == 1) return 1;
return inv(y % x, y) * (y - y / x) % y;
}
int main()
{
while(scanf("%d", &n) != EOF){
scanf("%s", s);
int len = strlen(s);
dp[0] = 1;
for(int i = 1; i
对字符串s，从左到右，对每个字串存储其哈希值dp。如果只考虑乘法的消耗，这一步的时间复杂度是O(len(s))。
对于任一子串，子串 S(a...b)的 hash 值： H(s)=dp[b]/dp[a−1]%mod
1/dp[a−1]%9973就是dp[a-1]的逆元。求逆元的时间复杂度是O(log(9973))，可看做O(1)。
这样的好处是：当N很大时，对于每对a、b，需要计算一个逆元和一次乘法。N次的时间复杂度是O(N)。
优化后的代码，总共的时间复杂度是O(N+len(s))。其中1≤N≤1,000，1≤len(s)≤100,000。
我的代码的劣势在于：当N很大时，对于每一对a和b，都要计算（b-a+1）次乘法。事实上，要询问的N个子川之间 很可能有很多重叠的地方，然而我的代码却每次都要重新计算重叠子串。所以优化后的代码避免了很多次重复的乘法运算。
我的代码时间复杂度是O(N(b-a+1))。当b-a+1趋向于len(s)时，达到最坏情况，此时复杂度是O(Nlen(s))。当所有的b==a时，达到最好情况，时间复杂度是O(N)。
显然，时间性能极不稳定，当b和a的差较大时，优化后的代码优势明显。
关于逆元的计算
关于优化代码中的逆元的计算公式的推导，参见博客《逆元详解》。
c++
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！