编码-百度之星资格赛Problem A-2016.05.14

2016-05-15 11:37:00

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

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

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的差较大时，优化后的代码优势明显。