题解：P13867 [SWERC 2020] Unique Activities

· · 题解

题目简述

给定一个字符串 s，求 s 最短没有重复出现的子串，若有多个长度相同的子串，输出起始位置最小的那个。

思路

令 \vert s \vert = n。

首先注意到一个性质，如果存在合法的长度为 l 的子串，那么也一定存在合法的长度为 l+1 的子串。其实就是个小思维点，画图考虑将所有长度为 l 的子串往后延伸一个就很显然了。

那么，我们就可以二分答案 l。对于所有长度为 l 的子串，看是否有只出现了一次的子串，可以用哈希 + map 判断。

时间复杂度

#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using ll = long long;

const int MAXN = 3e5 + 5, BASE = 64007;
const ll MOD = 2999999929;

int n;
ll power[MAXN], h[MAXN];
string s;
unordered_map<ll, int> cnt;

int Query(int l, int r){
  return (h[r] - h[l - 1] * power[r - l + 1] % MOD + MOD) % MOD;
}

int Check(int len){
  cnt.clear();
  for(int i = 1; i <= n - len + 1; i++){
    cnt[Query(i, i + len - 1)]++;
  }
  for(int i = 1; i <= n - len + 1; i++){
    if(cnt[Query(i, i + len - 1)] == 1) return i;
  }
  return 0;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> s;
  n = s.size(), s = "#" + s;
  power[0] = 1;
  for(int i = 1; i <= n; i++){
    power[i] = power[i - 1] * BASE % MOD;
    h[i] = (h[i - 1] * BASE % MOD + s[i] - 'A') % MOD;
  }
  int l = 0, r = n;
  while(l < r){
    int mid = (l + r) >> 1;
    Check(mid) ? r = mid : l = mid + 1;
  }
  cout << s.substr(Check(l), l);
  return 0;
}

后记

给一些字符串哈希的小技巧吧，适合一些哈希新手。

虽然这题不卡哈希，但是不难想到 CF 特别喜欢拐卖 998244353，10^9+7，19260813 这些常用质数，考场上怎么避免被卡呢？

当然你可以使用双哈希，但是码量翻倍，当你懒的再找质数是个好办法。

也可以赛前积累一些怪异质数，比如 993244853，1145140019，最好好记且不广为人知。

不过我经常临场找，我们知道 1 \sim n 中质数的个数约为 O(\frac{n}{\ln n})，那么大约每 \ln n 个数就会有一个质数！那么我们不妨随机从一个数 x 往后找，一直找到质数为止，这样大概找 \ln x 次就可以找到，暴力判断质数即可，一两分钟就可以找到一个较好的质数，像这样：

#include<bits/stdc++.h>

using namespace std;

int n;

bool Check(int n){
  if(n <= 2) return n == 2;
  for(int i = 2; i * i <= n; i++){
    if(n % i == 0) return 0;
  }
  return 1;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  while(!Check(n)) n++;
  cout << n;
  return 0;
}