首页 > 代码库 > bnuoj 34990(后缀数组 或 hash+二分)
bnuoj 34990(后缀数组 或 hash+二分)
后缀数组倍增算法超时，听说用3DC可以勉强过，不愿写了,直接用hash+二分求出log(n)的时间查询两个字符串之间的任意两个位置的最长前缀.
我自己在想hash的时候一直在考虑hash成数值时MOD取多大，如果取10^18的话，那么两数相乘个就超LL了，但是取10^9的话又怕出现重复的可能大.后面才发现自己是sb，如果用unsigned long long 如果有溢出或者为负数是直接变成对(1<<64)取模了。 也就是无符号长整形运算自动帮你取模了。所以可以放心用hash
Justice String
Time Limit: 2000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: MainPrev
Submit Status Statistics Discuss
NextGiven two strings A and B, your task is to find a substring of A called justice string, which has the same length as B, and only has at most two characters different from B.
Input
The first line of the input contains a single integer T, which is the number of test cases.
For each test case, the first line is string A, and the second is string B.
Both string A and B contain lowercase English letters from a to z only. And the length of these two strings is between 1 and 100000, inclusive.
Output
For each case, first output the case number as "Case #x: ", and x is the case number. Then output a number indicating the start position of substring C in A, position is counted from 0. If there is no such substring C, output -1.
And if there are multiple solutions, output the smallest one.
Sample Input
3aaabcdabeeaaaaaaaaaaaaaaaaaaabbb
Sample Output
Case #1: 2Case #2: 0Case #3: -1
Source
2014 ACM-ICPC Beijing Invitational Programming Contest
#include <iostream>#include <stdio.h>#include <string.h>#include <string>#include <algorithm>#include <math.h>#include <stdlib.h>using namespace std;#define N 100100#define KEY 31typedef unsigned long long ul;char a[N],b[N];ul base[N];ul hha[N],hhb[N];int lena,lenb;ul gethash(int x,int y,ul g[]){ if(x>y) return 0; return g[x]-g[y+1]*base[y+1-x];}int lcp(int pa,int pb)//求a串以pa为起始，与b串以pb为起始，最长的前缀{ int b=0,d=lenb-pb;//最小一个相同的都没有，最多有lenb个 while(b<d) { int mid=(b+d+1)/2; if( gethash(pa,pa+mid-1,hha)==gethash(pb,pb+mid-1,hhb) ) b=mid; else d=mid-1; } return b;}int main(){ int T; int tt=1; long long tmp=1; for(int i=0;i<N;i++) { base[i]=tmp; tmp*=KEY; } scanf("%d",&T); while(T--) { scanf("%s%s",a,b); lena=strlen(a); lenb=strlen(b); memset(hha,0,sizeof(hha)); memset(hhb,0,sizeof(hhb)); hha[lena]=0; for(int i=lena-1;i>=0;i--) hha[i] = hha[i+1]*KEY+a[i]-‘a‘; hhb[lenb]=0; for(int i=lenb-1;i>=0;i--) hhb[i] = hhb[i+1]*KEY+b[i]-‘a‘; int ans=-1; for(int i=0;i<=lena-lenb;i++) { int cnt=0; cnt += lcp(i+cnt,cnt); if(cnt>=lenb) { ans=i; break; } cnt++; if(cnt>=lenb) { ans=i; break; } cnt += lcp(i+cnt,cnt); if(cnt>=lenb) { ans=i; break; } cnt++; if(cnt>=lenb) { ans=i; break; } cnt += lcp(i+cnt,cnt); if(cnt>=lenb) { ans=i; break; } } printf("Case #%d: ",tt++); printf("%d\n",ans); //printf("%d %s\n",ans,a+ans); } return 0;}
bnuoj 34990(后缀数组 或 hash+二分)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。