Codeforces Round #254 (Div. 1) D - DZY Loves Strings

思路：感觉这种把询问按大小分成两类解决的问题都很不好想。。
题解说得很清楚啦。
#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 1e5 + ;

const int M = 1e6 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const double PI = acos(-);

int n, B;

string s, str;

string p[N], q[N];

int hsp[N], hsq[N], mn[M], len[M];

int gg[N][];

vector<int> vc[M];

bool vis[M];

int ans[N];

inline int get_hash(string& a) {

    int ans = ;

    for(int i = ; i < a.size(); i++)

        ans *= , ans += a[i]-'a'+;

    return ans;

}

int Merge(vector<int>& a, vector<int>& b, int lena, int lenb) {

    int ans = inf;

    if(!a.size() || !b.size()) return ans;

    for(int i = , j = ; i < a.size(); i++) {

        while(j+ < b.size() && a[i] >= b[j]) j++;

        if(j- >= ) ans = min(ans, max(a[i]+lena, b[j-]+lenb) - min(b[j-], a[i]));

        ans = min(ans, max(a[i]+lena, b[j]+lenb) - min(b[j], a[i]));

    }

    return ans;

}

int main() {

    memset(gg, -, sizeof(gg));

    memset(ans, inf, sizeof(ans));

    cin >> s;

    scanf("%d", &n);

    B = ceil(*s.size() / sqrt(n));

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

        cin >> p[i] >> q[i];

        hsp[i] = get_hash(p[i]);

        hsq[i] = get_hash(q[i]);

    }

    for(int i = ; i < s.size(); i++) {

        str = s.substr(i, );

        while(str.size()) {

            int hs = get_hash(str);

            vc[hs].push_back(i);

            len[hs] = str.size();

            gg[i][str.size()] = hs;

            str.pop_back();

        }

    }

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

        if(vc[i].size() >= B) {

            for(int j = ; j <= n; j++) mn[hsp[j]] = mn[hsq[j]] = inf;

            for(int j = , k = ; j < s.size(); j++) {

                while(k+ < vc[i].size() && j >= vc[i][k]) k++;

                for(int z = ; z <= ; z++) {

                    int hs = gg[j][z];

                    if(hs == -) continue;

                    if(k- >= ) mn[hs] = min(mn[hs], max(vc[i][k-]+len[i], j+len[hs]) - min(j, vc[i][k-]));

                    mn[hs] = min(mn[hs], max(vc[i][k]+len[i], j+len[hs]) - min(j, vc[i][k]));

                }

            }

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

                if(hsp[j] == i) ans[j] = min(ans[j], mn[hsq[j]]), vis[j] = true;

                else if(hsq[j] == i) ans[j] = min(ans[j], mn[hsp[j]]), vis[j] = true;

            }

        }

    }

    int cnt = , mx = ;

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

        if(!vis[i])

            ans[i] = Merge(vc[hsp[i]], vc[hsq[i]], len[hsp[i]], len[hsq[i]]);

    }

    for(int i = ; i <= n; i++) printf("%d\n", ans[i] == inf ? - : ans[i]);

    return ;

}

/*

*/
秒客网

Codeforces Round #254 (Div. 1) D - DZY Loves Strings

相关文章
