HDU 4821 String 字符串hash
2024-08-27 15:39:49
String
Problem Description
Given a string S and two integers L and M, we consider a substring of S as “recoverable” if and only if
(i) It is of length M*L;
(ii) It can be constructed by concatenating M “diversified” substrings of S, where each of these substrings has length L; two strings are considered as “diversified” if they don’t have the same character for every position.
(i) It is of length M*L;
(ii) It can be constructed by concatenating M “diversified” substrings of S, where each of these substrings has length L; two strings are considered as “diversified” if they don’t have the same character for every position.
Two substrings of S are considered as “different” if they are cut from different part of S. For example, string "aa" has 3 different substrings "aa", "a" and "a".
Your task is to calculate the number of different “recoverable” substrings of S.
Input
The input contains multiple test cases, proceeding to the End of File.
The first line of each test case has two space-separated integers M and L.
The second ine of each test case has a string S, which consists of only lowercase letters.
The length of S is not larger than 10^5, and 1 ≤ M * L ≤ the length of S.
Output
For each test case, output the answer in a single line.
Sample Input
3 3
abcabcbcaabc
abcabcbcaabc
Sample Output
2
题意:
给你M和L,和一个字符串S。
要求找出S的子串中长度为L*M,并且可以分成M段,每段长L,并且M段都不相同的子串个数。
题解:
枚举起点
hash每个前缀串
那么一段子串的hash值就可以快速求出
twopointsO(n)求出长度M*L,,M个连续串是否相同
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
typedef unsigned long long ULL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N = 5e5+, MM = 1e3+,inf = 2e9; const LL mod = 10000019ULL;
inline LL read()
{
LL x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} map<ULL,int > s;
ULL bhas[N],has[N],sqr[N];
int M,L;
char sa[N];
int vis[N];
int main() {
sqr[] = ;
for(int i = ; i < N; ++i) sqr[i] = sqr[i-] * mod;
while(scanf("%d%d",&M,&L)!=EOF) {
scanf("%s",sa+);
int n = strlen(sa+);
has[] = ;
for(int i = ; i <= n; ++i) {
has[i] = has[i-] * mod + sa[i] - 'a' + ;
}
int ans = ;
for(int i = ; i <= L && i + M * L - <= n; ++i) {
int cnt = ;
s.clear();
int ll = ,rr = ;
for(int j = i; j + L - <= n; j += L) {
int l = j, r = j + L - ;
ULL now = has[r] - has[l-]*sqr[L];
if(s[now] == ){
bhas[++rr] = now;
if(rr - ll + >= M)ans+=;
s[now] = ;
continue;
}
else {
while(ll <= rr && bhas[ll]!=now) {
s[bhas[ll++]] = ;
}
s[bhas[ll++]] = ;
bhas[++rr] = now;
if(rr - ll + >= M)ans+=;
s[now] = ;
}
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- jquery json ajax
- SQL Server数据库中还原孤立用户的方法集合
- jquery ajax 实例
- openNebula Image上传
- c# in deep 之LINQ简介(1)
- JQUERY写大图轮播;附jquery的hover()方法、animate()方法、find()方法
- forEach、map、filter、some、every五个数组方法
- AngularJs 第三节随笔
- html逻辑运算符
- 浅谈JS中的高级函数
- oracle pl/sql如何定义变量
- angularjs 设置全局变量(constant)
- scrapy框架Selector提取数据
- 自学huawei之路-AC6005-8AP添加授权码
- 用python处理文本,本地文件系统以及使用数据库的知识基础
- 全键盘操作Windows
- Crawl(2)
- 【BZOJ 2437】 2437: [Noi2011]兔兔与蛋蛋 (博弈+二分图匹配**)
- Boost::lexical_cast类型转换
- markdown与html之间转换引发的问题
热门文章
- php 注册与登录
- (转)新ITC提交APP常见问题与解决方法(Icon Alpha,Build version,AppIcon120x120)(2014-11-17)
- nginx进程属主问题讨论
- 【leetcode 字符串】466. Count The Repetitions
- R语言入门-画图(二)--heatmap
- Python入门--11--自定义函数
- 使用 ftrace 调试 Linux 内核,第1部分
- Maven实战:Pom.xml详解
- ELK之Kibana部署、收集系统日志、一个文件收集多个日志
- ios 处理内存警告