HDU 4821 字符串哈希+尺取+map操作

题意： 给两个正整数$M，L$，分别代表取$M$个长度为$L$的字符串，然后给任意长度的字符串，问：可以得到多少个由$M$个长度为$L$的不同字符串组成的$recoverable$。

思路： 用字符串哈希预处理字符串，然后枚举$1...L$里的点，以其做为起点，来处理字符串哈希值，然后用$map$进行统计长度为$M\ast L$的字符串是否合法的数量，进行尺取操作即可。

参考代码：

/* * @Author: vain * @Date: 2020-08-26 11:58:46 * @LastEditTime: 2020-09-04 10:00:26 * @LastEditors: sueRimn * @Description: In User Settings Edit * @FilePath: \main\demo.cpp */ #include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <math.h> #include <bitset> using namespace std; typedef long long ll; //#define ll long long typedef unsigned long long ull; const ll N = 2e3 + 20; const ll maxn = 1e5 + 20; const ll mod = 1e9 + 7; ll head[maxn], stac[maxn]; ll a[maxn], b[N], c[maxn], cnt; //typedef pair<ll, ll> p; //priority_queue<p, vector<p>, greater<p> > m; //ll sum[maxn]; ll max(ll a, ll b) { return a > b ? a : b; } ll min(ll a, ll b) { return a < b ? a : b; } ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a * b / gcd(a, b); } void swap(ll &x, ll &y) { x ^= y, y ^= x, x ^= y; } map<string, ll> pll, che, mp; ll f[N][N]; int lowbit(int x) { return (x) & (-x); } vector<string> fc; ull h[maxn], p[maxn]; const ull base = 13331; char s1[maxn]; ll ksm(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res *= a; b >>= 1; a *= a; } return res; } ull get(ull l, ull r) { return h[r] - h[l - 1] * p[r - l + 1]; } map<ull, ull> vis; string s[maxn]; int np[30][maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); srand(time(NULL)); ll n, m, ans; while (cin >> m >> n) { ans = 0; cin >> (s1 + 1); ll len = strlen(s1 + 1); //cout << len << endl; p[0] = 1; for (int i = 1; i <= len; i++) { h[i] = h[i - 1] * base + s1[i] - 'a' + 1; p[i] = p[i - 1] * base; } for (int i = 1; i <= n && i + m * n - 1 <= len; i++) { vis.clear(); for (int j = i; j <= i + m * n - 1; j += n) vis[get(j, j + n - 1)]++; if (vis.size() == m) ans++; //cout << ans << endl; for (int j = i + m * n; j + n - 1 <= len; j += n) { vis[get(j, j + n - 1)]++; vis[get(j - m * n, j - m * n + n - 1)]--; if (!vis[get(j - m * n, j - m * n + n - 1)]) vis.erase(get(j - m * n, j - m * n + n - 1)); if (vis.size() == m) ans++; } } cout << ans << endl; } }