【HDU-6192】Removing Mountains【扩展KMP+hash】

【HDU-6192】Removing Mountains【扩展KMP+hash】

问题链接:https://vjudge.net/problem/HDU-6192

Solution:

F题拆完墙,这道K题又要移山了。。。回到正题,问题要求输出最短周期以及改造的山个数。问题当然要一步一步解决,先从最特殊的情况入手,如果当前只有一座山,则最短周期必然使是1,由于题目都明确要求他非得移山了,那只有一座山,他若想移那就移吧,所以\(n = 1\)时,输出“1 1”。。。【个人觉得,这是这道题最坑的地方】接着,如果这座山已经存在周期了,那么只好把它们全部移除来破掉旧的周期,达到最小的周期,所以输出“1 n”。接着就是一般情况了,枚举每种周期,根据扩展kmp得到的最大相同前缀长度,尝试修改其失配的第一个位置(两种修改方法,为了方便表述,假设现在枚举到周期i,用扩展kmp打出的数组【我命名成了kmp[]】中kmp[i]就表示从字符i到字符串结尾的子串与原字符串的最大相同前缀长度,则说明字符串【我命名为str】的str[kmp[i]]与str[kmp[i] + i]失配,两种修改方法就是拿前者替换后者,或者后者替换前者),接着使用hash值来判是否相同(这道题字符集很小,hash值不用取模,只要进制素数取得足够大,就不会发生碰撞,直接用hash值判断就可以确定字符串相同,关于hash进行字符串匹配,可以阅读:Rabin-Karp Algorithm,需要留意的一点是,链接的这篇文章中hash值存在碰撞的可能,所以需要在hash值匹配后进行二次判断)。

#include <iostream>
#include <string>

using namespace std;

typedef unsigned long long LL;
const int LIM = 1e6 + 10;
const int BASE = 131;
string str;
int kmp[LIM], n;
LL carryNum[LIM];
LL prehash[LIM];

// use ch to replace the character pos at br(beReplace)
inline LL getHash(int l, int r, int br, char ch) {
    return prehash[r] - (l > 0 ? prehash[l - 1] * carryNum[r - l + 1] : 0)
        + (l <= br && br <= r ? -str[br] * carryNum[r - br] + ch * carryNum[r - br] : 0);
}

void init() {
    int i;
    for (carryNum[0] = 1, prehash[0] = str[0], i = 1; i < n; i++) {
        carryNum[i] = carryNum[i - 1] * BASE;
        prehash[i] = prehash[i - 1] * BASE + str[i];
    }
}

void exkmp() {
    kmp[0] = n;
    int i;
    for (i = 1; i < n && str[i - 1] == str[i]; i++);
    kmp[1] = i - 1;
    int p0 = 1;
    for (i = 2; i < n; i++) {
        if (i + kmp[i - p0] >= p0 + kmp[p0]) {
            int j = p0 + kmp[p0] - i;
            if (j < 0) j = 0;
            for (; j + i < n && str[j + i] == str[j]; j++);
            kmp[i] = j;
            p0 = i;
        } else {
            kmp[i] = kmp[i - p0];
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    while (cin >> n >> str) {
        if (n == 1) {
            cout << 1 << " " << 1 << endl;
            continue;
        }
        init();
        exkmp();
        for (int i = 1; i < n; i++) {
            int lca = kmp[i];
            if (i + lca == n) {
                cout << i << " " << n << endl;
                break;
            } else {
                int k = 0;
                if (getHash(0, n - 1 - i, lca, str[i + lca]) == getHash(i, n - 1, lca, str[i + lca]))
                    k++;
                if (getHash(0, n - 1 - i, i + lca, str[lca]) == getHash(i, n - 1, i + lca, str[lca]))
                    k++;
                if (k) {
                    cout << i << " " << k << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

 

解决这道题时去网上参考了一些大神的博文,十分感谢大佬的分享,参考链接附上:

https://blog.csdn.net/u012345506/article/details/80134756