首页 > 代码库 > POJ 2758 Checking the Text（Hash+二分答案）
POJ 2758 Checking the Text（Hash+二分答案）
【题目链接】 http://poj.org/problem?id=2758
【题目大意】
给出一个字符串，支持两个操作，在任意位置插入一个字符串，或者查询两个位置往后的最长公共前缀，注意查询的时候是原串下标，插入的时候则是最近更新串的下标。
【题解】
因为插入操作只有两百次，所以考虑hash重构来处理匹配问题，碰到插入就重构插入点往后的哈希表，否则二分两个位置往后的匹配长度，查hash表判断是否可行。
【代码】
#include <cstdio>#include <algorithm>#include <cstring>using namespace std; const int N=60000,base=233;typedef long long ll;int len,n,m,pos[N],x,y;ll hash[N],p[N];char s[N],op[10];void Build(int x){for(int i=x;i<=len;i++)hash[i]=hash[i-1]*base+s[i];} ll get_hash(int L,int R){return hash[R]-hash[L-1]*p[R-L+1];}int query(int x,int y){ int l=0,r=len-max(x,y)+1; while(l<=r){ int mid=l+r>>1; if(get_hash(x,x+mid-1)==get_hash(y,y+mid-1))l=mid+1; else r=mid-1; }return r; } int main(){ for(int i=p[0]=1;i<N;i++)p[i]=p[i-1]*base; scanf("%s",s+1); n=len=strlen(s+1); scanf("%d",&m); Build(1); for(int i=1;i<=n;i++)pos[i]=i; for(int i=1;i<=m;i++){ scanf("%s",op); if(op[0]==‘I‘){ scanf("%s%d",op,&x); if(x>len)x=len+1; memcpy(s+x+1,s+x,(len-x+1)*sizeof(char)); s[x]=op[0]; for(int j=n;j>=1;j--){ if(pos[j]>=x)pos[j]++; else break; }len++; Build(x); }else{ scanf("%d%d",&x,&y); printf("%d\n",query(pos[x],pos[y])); } }return 0;}
POJ 2758 Checking the Text（Hash+二分答案）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。