BUCTOJ String(Hash,二分)
程序员文章站
2022-06-02 17:45:11
...
思路
我们可以二分一下答案的长度,然后在判断当前长度是否可行。
因为T
串是S
串的子串,所以一定会匹配。利用Hash
记录一下当前枚举的串出现了几次,记录一下当前枚举的串上次出现的位置。当串出现的次数>=k的时候就证明当前枚举的长度可行
代码
#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 100;
unordered_map<string, int> cnt, pos;
string s, tmp;
int k, len;
int judge(int mid)
{
cnt.clear();
pos.clear();
for (int i = 0; i <= len - mid; i++)
{
if (i == 0)
tmp = s.substr(0, mid);
else
{
tmp.erase(tmp.begin());
tmp += s[i + mid - 1];
}
if (cnt[tmp] == 0 || pos[tmp] + mid - 1 < i)
{
pos[tmp] = i;
cnt[tmp]++;
}
if (cnt[tmp] >= k)
return 1;
}
return 0;
}
int main()
{
// freopen("in.txt", "r", stdin);
while (cin >> k)
{
cin >> s;
len = s.size();
int l = 1, r = len / k;
int ans = 0;
while (l <= r)
{
int mid = (l + r) >> 1;
if (judge(mid))
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
printf("%d\n", ans);
}
return 0;
}
推荐阅读
-
Python操作redis实例小结【String、Hash、List、Set等】
-
BZOJ4698: Sdoi2008 Sandy的卡片(二分 hash)
-
查找算法(顺序查找、二分法查找、二叉树查找、hash查找)
-
Python操作redis实例小结【String、Hash、List、Set等】
-
【原创】详细案例解剖——浅谈Redis缓存的常用5种方式(String,Hash,List,set,SetSorted )
-
详解HASH【string】
-
PAT_甲级_1050 String Subtraction (20分) (C++)【签到题/二分查找/字符串处理】
-
LOJ#111. 后缀排序(二分 hash)
-
CodeForces - 817F Graph and String(dfs判二分图)
-
BZOJ1014: [JSOI2008]火星人prefix(splay 二分 hash)