2019湖南省赛 C.Distinct Substrings（哈希+二分，扩展KMP）

本文主要是介绍2019湖南省赛 C.Distinct Substrings（哈希+二分，扩展KMP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：
串的最后加上i以后，实际上加上了$n+1$个串，我们要减去重复的子串个数。
假设串加上$i$后，对于长度为$mid$的后缀发生重复，那么对于长度为$1...mid-1$的后缀也会发生重复，所以要判断有$mid$个重复子串，实际就是判断新串长度为$mid$的后缀和旧串某个长度为$mid$的后缀发生重复。这个过程具有单调性，所以可
以哈希+二分写。

判断长度为$mid$，且以$i$为结尾的后缀是否在原串中发生重复，除了用哈希，还要对每个数建立个邻接表定位其出现的位置，以此减少复杂度。

$upd:$
按照上面的解法，实质上是求新串与旧串某个前缀的最大公共后缀，将串反一下，问题就变成了求新串与旧串所有后缀的最大公共前缀，这就成了扩展KMP裸题了。

ps:在牛客上这题内存不稳定，算好的5e6的int数组前面几次超内存，后面再交就A了，很迷。

哈希+二分

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 7;
const ll Base = 7537;
int n,m;
int head[maxn],nex[maxn];
int h[maxn],base[maxn];
int p[maxn];int get(int l,int r) {return ((h[r] - 1ll * h[l - 1] * base[r - l + 1] % mod) % mod + mod) % mod;
}bool check(int mid,int x) {int h1 = get(n + 1 - mid + 1,n + 1);for(int i = head[x];i && i >= mid;i = nex[i]) {int h2 = get(i - mid + 1,i);if(h1 == h2) return true;}return false;
}int main() {p[0] = 1;base[0] = 1;for(int i = 1;i < maxn;i++) {p[i] = 1ll * p[i - 1] * 3 % mod;base[i] = 1ll * base[i - 1] * Base % mod;}while(~scanf("%d%d",&n,&m)) {for(int i = 1;i <= m;i++) {head[i] = 0;}for(int i = 1;i <= n;i++) {int x;scanf("%d",&x);h[i] = (1ll * h[i - 1] * Base % mod + x) % mod;nex[i] = head[x];head[x] = i;}ll ans = 0;for(int i = 1;i <= m;i++) {h[n + 1] = (1ll * h[n] * Base % mod + i) % mod;int l = 0,r = n,res = 0;if(!head[i]) {res = 0;} else {while(l <= r) {int mid = (l + r) >> 1;if(check(mid,i)) {l = mid + 1;res = mid;} else {r = mid - 1;}}}ans ^= 1ll * p[i] * (n + 1 - res) % mod;}printf("%lld\n",ans);}return 0;
}

扩展KMP写法

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 3;
const int mod = 1e9 + 7;
int n, m, z[maxn],p[maxn];
int a[maxn],head[maxn],nex[maxn];inline void Z() {for (int i = 1; i <= n; i++) z[i] = 0;z[1] = n;for (int i = 2, l = 0, r = 0; i <= n; i++) {if (i <= r) z[i] = min(z[i-l+1], r - i + 1);while (i + z[i] <= n && a[i+z[i]] == a[z[i]+1]) ++z[i];if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;}
}int main() {p[0] = 1;for(int i = 1;i < maxn;i++) {p[i] = 1ll * p[i - 1] * 3 % mod;}while(~scanf("%d%d",&n,&m)) {for(int i = 1;i <= m;i++) {head[i] = 0;}for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);}reverse(a + 1, a + 1 + n);for(int i = 1;i <= n;i++) {nex[i] = head[a[i]];head[a[i]] = i;}Z();z[n + 1] = 0;ll ans = 0;for(int i = 1;i <= m;i++) {int now = i;int mx = 0;for(int j = head[now];j;j = nex[j]) {mx = max(mx,z[j + 1] + 1);}
//            printf("%d: %d\n",i,mx);ans ^= 1ll * p[i] * (n + 1 - mx) % mod;}printf("%lld\n",ans);}return 0;
}

这篇关于2019湖南省赛 C.Distinct Substrings（哈希+二分，扩展KMP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---