URAL1486 - Equal Squares

2016/10/15

上午看了一下冬令营论文《Hash函数在信息学竞赛中的一类应用》,主要讲这个增量哈希在字符串匹配上的应用。

然后例题就是这个辣!

主要解题思路是把一维的Rabin-Karp改成二维的。

二维的不好用 LaTeX 写出来,所以说直接扔代码XDDDDD

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int MAX_NM = 500 + 10;
const int SIZE   = MAX_NM * MAX_NM;
const ULL P1 = 101;
const ULL P2 = 999991;
const ULL Q1 = 45293;
const ULL Q2 = 37;   // STO - Generate by SageMath -  OTZ
int N, M; char Mat[MAX_NM][MAX_NM];
ULL hash1[MAX_NM][MAX_NM], powp1[MAX_NM], powq1[MAX_NM];
ULL hash2[MAX_NM][MAX_NM], powp2[MAX_NM], powq2[MAX_NM];
int x1, y1, x2, y2;
typedef pair< pair<int, int>, pair<int, int> > PII;
PII hh[SIZE];
bool cmp(const PII &a, const PII &b) {
    if(a.first != b.first) return a.first < b.first;
    else return a.second < b.second;
}

bool check(int k) {
    int tot = 0; ULL h1, h2;
    for(int i=k;i<=N;i++) {
        for(int j=k;j<=M;j++) {
            h1 = hash1[i][j] - hash1[i][j-k] * powp1[k] - hash1[i-k][j] * powq1[k] + hash1[i-k][j-k] * powq1[k] * powp1[k];
            h1 = hash2[i][j] - hash2[i][j-k] * powp2[k] - hash2[i-k][j] * powq2[k] + hash2[i-k][j-k] * powq2[k] * powp2[k];
            ++tot;
            hh[tot].first = make_pair(h1, h2);
            hh[tot].second = make_pair(i - k + 1, j - k + 1);
        }
    }

    sort(hh + 1, hh + 1 + tot, cmp);

    for(int i=1;i<tot;i++) {
        if(hh[i].first == hh[i+1].first) {
            int isans = 1;
            for(int x=0;x<k;x++) {
                for(int y=0;y<k;y++) {
                    if(Mat[x+hh[i].second.first][y+hh[i].second.second] != Mat[x+hh[i+1].second.first][y+hh[i+1].second.second]) {
                        isans = 0; goto _end;
                    }
                }
            }

            _end: ;

            if(isans) {
                x1 = hh[i].second.first; y1 = hh[i].second.second;
                x2 = hh[i+1].second.first; y2 = hh[i+1].second.second;
                return true;
            }
        }
    }

    return false;
}

int binary(int L, int R) {
    while(L != R) {
        int Mid = (L + 1 + R) >> 1;
        if(check(Mid)) L = Mid;
        else R = Mid - 1;
    }
    if(check(L))
        return L;
    else for(int i=1;i<=L;i++) if(check(L - i)) return L - i;
    return L;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N >> M;

    // 预处理各种pow值
    powp1[0] = powq1[0] = powp2[0] = powq2[0] = 1;
    for(int i=1;i<=M;i++) powp1[i] = powp1[i-1] * P1;
    for(int i=1;i<=N;i++) powq1[i] = powq1[i-1] * Q1;
    for(int i=1;i<=M;i++) powp2[i] = powp2[i-1] * P2;
    for(int i=1;i<=N;i++) powq2[i] = powq2[i-1] * Q2;

    char c;
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=M;j++) {
            cin >> c; Mat[i][j] = c - 'a';
            hash1[i][j] = Mat[i][j] + hash1[i][j-1] * P1 + hash1[i-1][j] * Q1 - hash1[i-1][j-1] * P1 * Q1;
            hash2[i][j] = Mat[i][j] + hash2[i][j-1] * P2 + hash2[i-1][j] * Q2 - hash2[i-1][j-1] * P2 * Q2;
        }
    }

    int ans = binary(0, min(N, M));
    cout << ans << endl;
    if(ans) {
        cout << x1 << " " << y1 << endl
             << x2 << " " << y2 << endl;
    }
}

事实上这个代码很玄学,质数是拿 SageMath 随机出来的,交了WA掉好几次,原因是这个 Hash 有一定概率碰撞(X)

所以说检测到相同的hash之后暴力跑一遍cmp是坠吼的。。