NOIP 提高 2018 第一轮 第 23 题：四进制编码统计本质唯一子串

题目

```cpp
#include <iostream>
using namespace std;
string s;

long long magic(int l, int r) {
    long long ans = 0;
        for (int i = l; i <= r; ++i) {
        ans = ans * 4 + s[i] - ‘a’ + 1;
    }
return ans;
}

int main() {
    cin >> s;
    int len = s.length();
    int ans = 0;
    for (int l1 = 0; l1 < len; ++l1) {
        for (int r1 = l1; r1 < len; ++r1) {
            bool bo = true;
            for (int l2 = 0; l2 < len; ++l2) {
                for (int r2 = l2; r2 < len; ++r2) {
                    if (magic(l1, r1) == magic(l2, r2) 
                    	&& (l1 != l2 || r1 != r2)) 
                    	bo = false;
                }
            }
            
            if (bo) {
                ans += 1;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
```

输入：abacaba

阅读程序写结果：

答案

16

题解

考点定位

本题考「四进制哈希本质子串」,对应大纲 4.2.1 模拟（难度【5】）。

解题过程

magic(l,r) 把 s[l..r] 作四进制数；统计本质不同的 (l,r) 段数。输入 abacaba：逐段枚举去重：

子串 28 个中本质唯一（四进制编码无碰撞）的个数 = 16。

答案：16。

易错提醒

① 四进制编码把子串映射为数——不同子串可能同码（编码截断冲突），题目要求统计编码唯一性；② 手工按长度分层去重。