Harry And Biological Teacher 分块 + 字符串hash

http://acm.hdu.edu.cn/showproblem.php?pid=5069

首先判断suffix和prefix最长多少可以直接暴力枚举长度然后 +　ｈａｓｈ可以立马判断是否相等，复杂度O(lenstr)

现在知道总长度 <= 1e5，  magic = sqrt(lenstr)

那么，

如果长度是 <= magic的，最多1e5个询问，每次询问我暴力也是才1e5 * sqrt(1e5)的复杂度。

如果长度是 >= magic的，

第一个极端情况是有magic个不同的串，这样就可以有magic^2个不同的询问，但是这样每个串的长度最长是magic，这样暴力也是才magic * magic * magic  = 1e5 * sqrt(1e5)的复杂度。

第二个极端情况是只有2个串，每个串长度都很长，1e5 / 2 的长度，这样暴力一次就需要O(1e5)的复杂度了。但是如果这样的话，不同的询问就会很少，可以用个ans数组存起来,ans[a][b]，这样总复杂度也是 <= 1e5 * sqrt(1e5)的复杂度。

所以总复杂度是nsqrtn

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

const int maxn = 1e5 + ;

char str[maxn];

int po[maxn], suffix[maxn], prefix[maxn];

int be[maxn], en[maxn];

int n, q;

int ans[][];

int getAns(int one, int two) {

    for (int i = min(en[two] - be[two] + , en[one] - be[one] + ); i >= ; --i) {

        if (prefix[be[two] + i - ] == suffix[en[one] - i + ]) {

            return i;

        }

    }

    return ;

}

int pos[maxn];

void work() {

    scanf("%d%d", &n, &q);

    int magic = (int)sqrt(n * 1.0);

    int to = ;

    for (int i = ; i <= n; ++i) {

        scanf("%s", str + en[i - ] + );

        int len = strlen(str + en[i - ] + );

        be[i] = en[i - ] + , en[i] = en[i - ] + len;

        prefix[be[i]] = str[be[i]];

        for (int j = be[i] + ; j <= en[i]; ++j) {

            prefix[j] = prefix[j - ] *  + str[j];

        }

        suffix[en[i]] = str[en[i]];

        for (int j = en[i] - ; j >= be[i]; --j) {

            suffix[j] = str[j] * po[en[i] - j] + suffix[j + ];

        }

        if (len > magic) {

            pos[i] = ++to;

        }

    }

//    printf("%s\n", str + 1);

//    for (int i = 1; i <= n; ++i) {

//        printf("%d %d\n", be[i], en[i]);

//    }

    for (int i = ; i <= to; ++i) {

        for (int j = ; j <= to; ++j) {

            ans[i][j] = -;

        }

    }

    while (q--) {

        int one, two;

        scanf("%d%d", &one, &two);

        if (en[one] - be[one] +  <= magic || en[two] - be[two] +  <= magic) {

            printf("%d\n", getAns(one, two));

        } else {

            if (ans[pos[one]][pos[two]] == -) {

                ans[pos[one]][pos[two]] = getAns(one, two);

            }

            printf("%d\n", ans[pos[one]][pos[two]]);

        }

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    po[] = ;

    for (int i = ; i <= maxn - ; ++i) po[i] = po[i - ] * ;

    while (scanf("%d%d", &n, &q) > ) work();

    return ;

}

https://www.nowcoder.com/acm/contest/94/E

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef unsigned long long int LL;

const int maxn = 1e6 + ;

char str[maxn];

LL po[maxn], suffix[maxn], prefix[maxn];

int be[maxn], en[maxn];

int n, q;

int ans[][];

int getAns(int one, int two) {

    for (int i = min(en[two] - be[two] + , en[one] - be[one] + ); i >= ; --i) {

        if (prefix[be[two] + i - ] == suffix[en[one] - i + ]) {

            return i;

        }

    }

    return ;

}

int pos[maxn];

void work() {

    int magic = (int)sqrt( * 1.0);

    int to = ;

    for (int i = ; i <= n; ++i) {

        scanf("%s", str + en[i - ] + );

        int len = strlen(str + en[i - ] + );

        be[i] = en[i - ] + , en[i] = en[i - ] + len;

        prefix[be[i]] = str[be[i]];

        for (int j = be[i] + ; j <= en[i]; ++j) {

            prefix[j] = prefix[j - ] *  + str[j];

        }

        suffix[en[i]] = str[en[i]];

        for (int j = en[i] - ; j >= be[i]; --j) {

            suffix[j] = str[j] * po[en[i] - j] + suffix[j + ];

        }

        if (len > magic) {

            pos[i] = ++to;

        }

    }

//    printf("%s\n", str + 1);

//    for (int i = 1; i <= n; ++i) {

//        printf("%d %d\n", be[i], en[i]);

//    }

    for (int i = ; i <= to; ++i) {

        for (int j = ; j <= to; ++j) {

            ans[i][j] = -;

        }

    }

    cin >> q;

    while (q--) {

        int one, two;

        scanf("%d%d", &one, &two);

        if (en[one] - be[one] +  <= magic || en[two] - be[two] +  <= magic) {

            printf("%d\n", getAns(one, two));

        } else {

            if (ans[pos[one]][pos[two]] == -) {

                ans[pos[one]][pos[two]] = getAns(one, two);

            }

            printf("%d\n", ans[pos[one]][pos[two]]);

        }

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    po[] = ;

    for (int i = ; i <= maxn - ; ++i) po[i] = po[i - ] * ;

    while (scanf("%d", &n) > ) work();

    return ;

}