首页 > 代码库 > hdu 4644 BWT (kmp)
hdu 4644 BWT (kmp)
看完题目你很容易想到,这个题目的关键点就是如何把给出的数组还原成原数组。
还原的原数组之后不管是AC自动机 还是 kmp都可以解决 - -虽然我觉得kmp会超时的感觉。
那么如何还原这个字符串就是在个题目的难点。。。
gc$aaac
1234567
排序之后变成了
$aaaccg
3456271
然后你按照排序后的下标依次走过去
会发现
$->a->c->a->a->c->g
3 5 2 4 6 7
也就恢复了原串。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define maxn 100186 using namespace std; struct node { char ch; int index; bool operator < (const node & cmp)const { return ch<cmp.ch; } }save[maxn]; char t[maxn]; char str[maxn],txt[maxn]; int next[maxn]; void getnext(int len) { next[0]=0;next[1]=0; for(int i=1;i<len;i++) { int j=next[i]; while(j && txt[j]!=txt[i])j=next[j]; next[i+1]=txt[j]==txt[i]?j+1:0; } } void find(int n,int m) { int j=0; for(int i=0;i<n;i++) { while(j&&txt[j]!=str[i])j=next[j]; if(txt[j]==str[i])j++; if(j==m){printf("YES\n");return ;} } printf("NO\n"); } int main() { while(scanf("%s",t)!=EOF) { int len=strlen(t); for(int i=0;i<len;i++) { save[i].ch=t[i]; save[i].index=i; } stable_sort(save,save+len); int now=save[0].index; for(int i=0;i<len-1;i++) { str[i]=save[now].ch; now=save[now].index; } int q; scanf("%d",&q); while(q--) { scanf("%s",txt); int m=strlen(txt); getnext(m); find(len-1,m); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。