hdu3518 Boring counting
2024-08-29 13:15:38
地址:http://acm.split.hdu.edu.cn/showproblem.php?pid=3518
题目:
Boring counting
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3187 Accepted Submission(s): 1320
Problem Description
035 now faced a tough problem,his english teacher gives him a string,which consists with n lower case letter,he must figure out how many substrings appear at least twice,moreover,such apearances can not overlap each other.
Take aaaa as an example.”a” apears four times,”aa” apears two times without overlaping.however,aaa can’t apear more than one time without overlaping.since we can get “aaa” from [0-2](The position of string begins with 0) and [1-3]. But the interval [0-2] and [1-3] overlaps each other.So “aaa” can not take into account.Therefore,the answer is 2(“a”,and “aa”).
Take aaaa as an example.”a” apears four times,”aa” apears two times without overlaping.however,aaa can’t apear more than one time without overlaping.since we can get “aaa” from [0-2](The position of string begins with 0) and [1-3]. But the interval [0-2] and [1-3] overlaps each other.So “aaa” can not take into account.Therefore,the answer is 2(“a”,and “aa”).
Input
The input data consist with several test cases.The input ends with a line “#”.each test case contain a string consists with lower letter,the length n won’t exceed 1000(n <= 1000).
Output
For each test case output an integer ans,which represent the answer for the test case.you’d better use int64 to avoid unnecessary trouble.
Sample Input
aaaa
ababcabb
aaaaaa
#
Sample Output
2
3
3
Source
思路:
枚举所有可能的长度,然后在height数组中求出这样的子串有多少个
复杂度O(n^2)
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm> const int N = ;
int sa[N],s[N],wa[N], wb[N], ws[N], wv[N];
int rank[N], height[N]; bool cmp(int r[], int a, int b, int l)
{
return r[a] == r[b] && r[a+l] == r[b+l];
}
void calheight(int r[], int sa[], int n)
{
int i, j, k = ;
for (i = ; i <= n; ++i) rank[sa[i]] = i;
for (i = ; i < n; height[rank[i++]] = k)
for (k?k--:, j = sa[rank[i]-]; r[i+k] == r[j+k]; k++);
}
void da(int r[], int sa[], int n, int m)
{
int i, j, p, *x = wa, *y = wb;
for (i = ; i < m; ++i) ws[i] = ;
for (i = ; i < n; ++i) ws[x[i]=r[i]]++;
for (i = ; i < m; ++i) ws[i] += ws[i-];
for (i = n-; i >= ; --i) sa[--ws[x[i]]] = i;
for (j = , p = ; p < n; j *= , m = p)
{
for (p = , i = n - j; i < n; ++i) y[p++] = i;
for (i = ; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = ; i < n; ++i) wv[i] = x[y[i]];
for (i = ; i < m; ++i) ws[i] = ;
for (i = ; i < n; ++i) ws[wv[i]]++;
for (i = ; i < m; ++i) ws[i] += ws[i-];
for (i = n-; i >= ; --i) sa[--ws[wv[i]]] = y[i];
for (std::swap(x, y), p = , x[sa[]] = , i = ; i < n; ++i)
x[sa[i]] = cmp(y, sa[i-], sa[i], j) ? p- : p++;
}
calheight(r,sa,n-);
} int check(int lc,int x)
{
int mi=sa[],mx=sa[],ans=;
for(int i=;i<=lc;i++)
{
if(height[i]<x)
{
if(mx-mi>=x)
ans++;
mx=mi=sa[i];
}
else
{
mx=std::max(mx,sa[i]);
mi=std::min(mi,sa[i]);
}
}
if(mx-mi>=x)ans++;
return ans;
}
char ss[N];
int main()
{
while(scanf("%s",ss)==)
{
if(ss[]=='#')break;
int la=strlen(ss),n=,ans=;
for(int i=;i<la;i++)
s[n++]=ss[i]-'a'+;
s[n]=;
da(s,sa,n+,);
for(int i=;i<=n/;i++)
ans+=check(n,i);
printf("%d\n",ans);
}
return ;
}
最新文章
- MAC OS X El CAPITAN 搭建SPRING MVC (1)- 目录、包名、创建web.xml
- HTML 字符实体
- 用Intellij打可执行jar包
- HDOJ 4389 X mod f(x)
- Ubuntu 安装JDK步骤 ,提示没有那个文件或目录
- 20160805_Win7x64刻录CentOS6.4x64启动光盘
- Visual Studio创建跨平台移动应用_01.Cordova&;Xamarin
- android中使用jni对字符串加解密实现分析
- css 中的背景图片小技巧和存在的坑
- git学习——Github关联(2)
- T4模板简单了解
- javafx:JavaFX Scene Builder 2.0打开含有第三方jar包的fxml文件报错 Caused by: java.lang.ClassNotFoundException
- php curl使用 常用操作
- VSCode插件开发全攻略(七)WebView
- ansible笔记(8):常用模块之系统类模块(二)
- Luogu4546 THUWC2017 在美妙的数学王国中畅游 LCT、泰勒展开
- JAVA JDBC 增删改查简单例子
- 大数据-10-Spark入门之支持向量机SVM分类器
- Web 后端--PHP 与数据库的交互
- 【题解】洛谷P4180 [BJWC2010] 严格次小生成树(最小生成树+倍增求LCA)