大致题意:
给出两个字符串a,b和一个数字k,求出a中存在多少后缀,使得其和b中所有后缀的lcp的最大值等于k。
大致思路:
又弱智了的说,上来就用后缀数组+RMQ来爆,O(n^2)的效率果断TLE了,不要bs我……在网上看到的正解是先求出a中存在多少后缀,使得其和b的所有后缀的lcp最大值大于等于k,再求出a中存在多少后缀,使得其和b的所有后缀的lcp最大值大于等于k+1。求出这两个值之后相减即可……
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int nMax =1000000;
int num[nMax];
int sa[nMax], rank[nMax], height[nMax];
int wa[nMax], wb[nMax], wv[nMax], wd[nMax];
int cmp(int *r, int a, int b, int l){
return r[a] == r[b] && r[a+l] == r[b+l];
}
void da(int *r, int n, int m){ // 倍增算法 r为待匹配数组 n为总长度 m为字符范围
int i, j, p, *x = wa, *y = wb, *t;
for(i = 0; i < m; i ++) wd[i] = 0;
for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++;
for(i = 1; i < m; i ++) wd[i] += wd[i-1];
for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] = i;
for(j = 1, p = 1; p < n; j *= 2, m = p){
for(p = 0, i = n-j; i < n; i ++) y[p ++] = i;
for(i = 0; i < n; i ++) if(sa[i] >= j) y[p ++] = sa[i] - j;
for(i = 0; i < n; i ++) wv[i] = x[y[i]];
for(i = 0; i < m; i ++) wd[i] = 0;
for(i = 0; i < n; i ++) wd[wv[i]] ++;
for(i = 1; i < m; i ++) wd[i] += wd[i-1];
for(i = n-1; i >= 0; i --) sa[-- wd[wv[i]]] = y[i];
for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++){
x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1: p ++;
}
}
}
void calHeight(int *r, int n){ // 求height数组。
int i, j, k = 0;
for(i = 1; i <= n; i ++) rank[sa[i]] = i;
for(i = 0; i < n; height[rank[i ++]] = k){
for(k ? k -- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k ++);
}
}
int getnum1(int k,int l1,int l2){
int len=l1+l2+1,i,a=0,b=0,res=0;
for(i=2;i<=len;i++){
if(height[i]>=k){
a=b=0;
if(sa[i-1]<l1)a++;
if(sa[i-1]>l1)b++;
for(;height[i]>=k;i++){
if(sa[i]<l1)a++;
if(sa[i]>l1)b++;
}
if(b>0)res+=a;
}
}
return res;
}
int main(){
int i,j,a,b,mmax,k,n,ans;
while(scanf("%d%d%d",&a,&b,&k)!=EOF){
n=0;
ans=0;
for(i=0;i<a;i++){
scanf("%d",&num[n]);
num[n]++;
n++;
}
num[n++]=30000;
for(i=0;i<b;i++){
scanf("%d",&num[n]);
num[n]++;
n++;
}
num[n]=0;
da(num,n+1,40000);
calHeight(num,n);
ans=getnum1(k,a,b)-getnum1(k+1,a,b);
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1757060
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1754756
NULL 博文链接:https://128kj.iteye.com/blog/1746750
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
这是西北工业大学的POJ试题的答案,欢迎下载!
NULL 博文链接:https://128kj.iteye.com/blog/1747400
网上整理的一些poj刷题指南。 poj地址:http://poj.org
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
NULL 博文链接:https://128kj.iteye.com/blog/1745671
只是poj上的一条题目,对于理解后缀数组很有帮助.poj3261
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2388-Who's in the Middle 解题报告+AC代码
twilight-poj-solutionPOJ () solution by twilight想当年要找一题的分析, 解答实在太难了现在都是开源的时代了, 干脆把Archive放到GitHub上, 供后来人参考.POJ ID: 部分题解: 转载请注明出处~
北大POJ2262-Goldbach's Conjecture 解题报告+AC代码
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
leetcode 2 和 c 实践 C++ ###数据结构和算法 大批 加一: # 合并排序数组:# 排序 搜索 二分查找:代码、#、#、# 选择 数组中第 K 个最大元素:# 递归 ...动态规划:LeetCode#xx、POJ#xx 后缀数组
POJ 3267 POJ 1260 POJ 1015 POJ 3176 POJ 1080 POJ 1159 POJ 2533 POJ 1836 Leetcode 70 Leetcode 309 搜索 DFS POJ 2488 POJ 3083 POJ 3009 POJ 1321 BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索...
poj上的题,音乐主题,首先需要对给定的数组差分,之后就是用后缀数组就行