POJ2758 Checking the Text
2024-09-05 21:53:28
题目链接：https://vjudge.net/problem/POJ-2758
题目大意：
先给出一串原始字符串，在此基础上执行两种操作：
1、在第 p 个字符前添加字符 ch，如果 p 比现字符串的长度 nowlen 大，则添加到现字符串的末尾。注意，这里的所有位置都是相对于变化后的字符串而言的！
2、查询第 i 个和第 j 个后缀的最长公共前缀。注意，这里的位置是相对于原始字符串而言的。
解题思路：
这道题真的可以说是最近几个月我做的最痛苦的一道题之一了。真的很煎熬。
一开始，我的思路是后缀数组加模拟（因为实在 kuangbin 的后缀数组专题里面碰到的嘛~）。发现其实在这种做法中后缀数组作用并不大，主要的工作都在于模拟字符的添加和最长公共前缀的查询，后缀数组只不过是起到了加速的作用，而且模拟的过程及其之麻烦，感觉不是很自然，所以就去查了一眼题解，发现还真的有人用后缀数组做的，扫了几眼他的思路，好像也是后缀数组加暴力的做法。。。所以我决定自己动手写一版。。。然后。。。一场悲剧。。。真的是各种不好写。。。好不容易把它调到可以过我能找到的所有样例和我自己造的几组数据。。。但还是各种WA。。。真的好痛苦。。。整整一天都调不出来。。。在此贴上代码，以后哪天再回过头来看看吧：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm> using namespace std;
const int maxn=+,inf=0x7fffffff;
char inp[maxn];
int s[maxn];
int n,k;
int Rank[maxn],sa[maxn],tmp[maxn],height[maxn];
bool compare_sa(int i,int j){
if(Rank[i]!=Rank[j]) return Rank[i]<Rank[j];
else{
int ri=i+k<=n?Rank[i+k]:-;
int rj=j+k<=n?Rank[j+k]:-;
return ri<rj;
}
}
void construct_sa(){
for(int i=;i<=n;i++){
sa[i]=i;
Rank[i]=i<n?s[i]:-;
}
for(k=;k<=n;k*=){
sort(sa,sa+n+,compare_sa);
tmp[sa[]]=;
for(int i=;i<=n;i++){
tmp[sa[i]]=tmp[sa[i-]]+(compare_sa(sa[i-],sa[i])?:);
}
for(int i=;i<=n;i++){
Rank[i]=tmp[i];
}
}
}
void construct_height(){
int h=;
height[]=;
for(int i=;i<n;i++){
int j=sa[Rank[i]-];
if(h>) h--;
for(;j+h<n&&i+h<n;h++){
if(s[j+h]!=s[i+h]) break;
}
height[Rank[i]-]=h;
}
}
vector<int> add[];
set<int> inserts;
int main()
{
freopen("in.txt","r",stdin);
char ord[],ins[];
int have,a,b;
scanf("%s",inp);
n=strlen(inp);
int nowlen=n;
for(int i=;i<n;i++) s[i]=inp[i]-'A';
construct_sa();
construct_height();
scanf("%d",&have);
while(have--){
// for(int i=0;i<n;i++){
// if(inserts.count(i)){
// for(int j=0;j<add[i].size();j++) printf("%c",'A'+add[i][j]);
// }
// printf("%c",'A'+s[i]);
// }
// for(int i=0;i<add[n].size();i++) printf("%c",'A'+add[n][i]);
// printf("\n");
scanf("%s",ord);
if(ord[]=='Q'){
scanf("%d%d",&a,&b); //a<b
a--,b--;
if(a>b) swap(a,b);
int same=inf;
if(Rank[a]<Rank[b]){
for(int i=Rank[a];i<Rank[b];i++){
if(height[i]<same) same=height[i];
}
}
else{
for(int i=Rank[b];i<Rank[a];i++){
if(height[i]<same) same=height[i];
}
} bool go=true;
int ans=,last_a=a,last_b=b,last_a_in=,last_b_in=;
set<int>::iterator k1=inserts.upper_bound(a);
set<int>::iterator k2=inserts.upper_bound(b);
int p1=*k1,p2=*k2;
if(k1==inserts.end()) p1=inf;
if(k2==inserts.end()) p2=inf;
if(p1-a>same && p2-b>same){
printf("%d\n",same);
continue;
}
while(go){
// printf("p1: %d, p2: %d, ans: %d, last_b: %d, last_a: %d\n",p1,p2,ans,last_b,last_a);
if(p1-a>same && p2-b>same){
while(last_a<n&&last_b<n&&s[last_a++]==s[last_b++]) ans++;
break;
}
if(last_a_in&&last_b_in){
for(;last_a_in<add[p1].size()&&last_b_in<add[p2].size();last_a_in++,last_b_in++){
if(add[p1][last_a_in]!=add[p2][last_b_in]){
go=false; break;
}else ans++;
}if(!go) break;
if(last_a_in==add[p1].size()){
k1=inserts.upper_bound(p1);
last_a=p1,last_a_in=;
p1=*k1;
if(k1==inserts.end()) p1=inf;
}
if(last_b_in==add[p2].size()){
k2=inserts.upper_bound(p2);
last_b=p2,last_b_in=;
p2=*k2;
if(k2==inserts.end()) p2=inf;
}
}else if(last_a_in){
for(;last_a_in<add[p1].size()&&last_b<n&&last_b<p2;last_a_in++,last_b++){
if(add[p1][last_a_in]!=s[last_b]){
go=false; break;
}else ans++;
}if(!go) break;
if(last_a_in==add[p1].size()&&last_b==p2){
k1=inserts.upper_bound(p1);
last_a=p1,last_a_in=;
p1=*k1;
if(k1==inserts.end()) p1=inf; if(add[p2][last_b_in++]==s[last_a++]) ans++;
else{
go=false;
}
}else if(last_a_in==add[p1].size()){
k1=inserts.upper_bound(p1);
last_a=p1,last_a_in=;
p1=*k1;
if(k1==inserts.end()) p1=inf;
}else{
if(last_a_in<add[p1].size()&&last_b_in<add[p2].size()&&add[p2][last_b_in++]==add[p1][last_a_in++]) ans++;
else{
go=false;
}
}if(!go) break;
}else if(last_b_in){
for(;last_b_in<add[p2].size()&&last_a<n&&last_a<p1;last_b_in++,last_a++){
if(add[p2][last_b_in]!=s[last_a]){
go=false; break;
}else ans++;
}if(!go) break;
if(last_b_in==add[p2].size()&&last_a==p1){
k2=inserts.upper_bound(p2);
last_b=p2,last_b_in=;
p2=*k2;
if(k2==inserts.end()) p2=inf; if(add[p1][last_a_in++]==s[last_b++]) ans++;
else{
go=false;
}
}else if(last_b_in==add[p2].size()){
k2=inserts.upper_bound(p2);
last_b=p2,last_b_in=;
p2=*k2;
if(k2==inserts.end()) p2=inf;
}else{
if(add[p1][last_a_in++]==add[p2][last_b_in++]) ans++;
else{
go=false;
}
}if(!go) break;
}else{
if(p1-a<p2-b){
ans+=p1-last_a;
last_b+=(p1-last_a);
last_a=p1;
if(add[p1][last_a_in++]==s[last_b++]) ans++;
else
go=false;
}
else if(p1-a>p2-b){
ans+=p2-last_b;
last_a+=(p2-last_b);
last_b=p2;
if(add[p2][last_b_in++]==s[last_a++]) ans++;
else
go=false;
}
else{
if(p1<=n){
ans+=p1-last_a;
last_a=p1,last_b=p2;
if(add[p1][last_a_in++]==add[p2][last_b_in++]) ans++;
else
go=false;
}
else{
while(last_a<n&&last_b<n&&s[last_a++]==s[last_b++]) ans++;
go=false;
}
}
}
}
printf("%d\n",ans);
}
else{
scanf("%s %d",ins,&a);
a--;
// printf("nowlen: %d, a: %d\n",nowlen,a);
if(a>=nowlen){
add[n].push_back(ins[]-'A');
inserts.insert(n);
}
else{
int now=;
set<int>::iterator k3=inserts.upper_bound(now);
int last=*k3;
if(k3==inserts.end()) last=inf;
// printf("now: %d, last: %d\n",now,last);
if(last>a){
add[a].push_back(ins[]-'A');
inserts.insert(a);
}
else{
while(){
now=last-;
// printf("a: %d\n",a);
if(a-now>add[last].size()+){
a-=add[last].size();
now++;
k3=inserts.upper_bound(now);
last=*k3;
if(k3==inserts.end()) last=inf;
// printf("a: %d, now: %d, last: %d\n",a,now,last);
}
else if(a-now==add[last].size()+){
add[last].push_back(ins[]-'A');
break;
}
else{
// printf("pos: %d\n",a-now);
add[last].insert(add[last].begin()+a-now-,ins[]-'A');
break;
}
if(a-now<last-now){
add[a].push_back(ins[]-'A');
inserts.insert(a);
break;
}
}
}
}
++nowlen;
}
}
return ;
}
后来实在受不了了，在网上学了一种哈希的做法，二分又写挂了。。。好累。。。
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=;
unsigned long long hashs[maxn],pw[maxn];
char inp[maxn];
int len,old[maxn],nowlen;
void build(int s){
for(int i=s;i<=nowlen;i++)
hashs[i]=hashs[i-]*+inp[i];
} int query(int a,int b){
if(a>b) swap(a,b);
int l=,r=nowlen-b+,mid; //此处要把 l 和 r 之间的距离尽量压缩，不然会WA
int ans=;
while(l<r){
mid=(l+r+)/; //此处令mid稍微右偏，然后 r 修改的时候用 r=mid-1，稍微左偏，提高精度，不然也会WA
if(hashs[a+mid-]-hashs[a-]*pw[mid]==hashs[b+mid-]-hashs[b-]*pw[mid]) l=mid,ans=mid;
else r=mid-;
}
return ans;
}
int main(){
int have,a,b;
char ord[],ins[];
scanf("%s",inp+);
scanf("%d",&have);
nowlen=strlen(inp+);
len=nowlen;
pw[]=;
for(int i=;i<=len+;i++) pw[i]=pw[i-]*;
for(int i=;i<=len;i++) old[i]=i;
build();
for(int j=;j<have;j++){
scanf("%s",ord);
if(ord[]=='Q'){
scanf("%d%d",&a,&b);
printf("%d\n",query(old[a],old[b]));
}
else{
scanf("%s %d",ins,&a);
if(a>nowlen) a=nowlen+;
for(int i=nowlen;i>=a;i--) inp[i+]=inp[i];
inp[a]=ins[];nowlen++;
build(a);
for(int i=len;i>=;i--){
if(old[i]>=a) old[i]++;
else break;
}
}
}
return ;
}
最新文章
- Adaboost提升算法从原理到实践
- Smack 3.3.1 发布，Java 的 XMPP 开发包
- 20145308刘昊阳 《Java程序设计》第3周学习总结
- IconVault – 创建自定义图标字体的神器推荐
- Office文件上传自动生成缩略图
- AngularJs-指令和控制器交互
- CentOS下启动Tomcat
- UVa 11584 Partitioning by Palindromes
- html 如何引入一个公共的头部和底部
- 【模拟】XMU 1054 Hacker
- cf459E Pashmak and Graph
- Python从json中提取数据
- JVM 调优系列之图解垃圾回收
- Groovy入门（2-2）Groovy的eclipse插件安装
- img添加预加载图片
- python基础 ---- 安装
- SQL 查看SQL语句的执行时间 直接有效的方法
- Python选修课第一届Turtle绘图大赛田康林赵冰珂组
- Android中实现延时执行操作的几种方法
- https协议的接口测试