ZOJ-3430 AC自动机+恶心...

ZOJ-3430 AC自动机+恶心...

这道题要留意的是转换后的字符,是0~255的..包括一些转义字符..譬如'\0'的..so..用字符串存会很囧..所以用int数组存...

本题分为两步...第一步是翻译字符串...第二步是AC自动机...

我对位运算很不熟练...所以在翻译字符串用的是最原始最原始的方法...先将字符串读入..转化为二进制串..再翻译成所需的...还好...虽然效率不高..但也没耽误太多时间..

第二步就是AC自动机模板题了...有好几个月没写AC自动机...发现自己写出来的和以前完全不同了...但感觉现在写的这个更为有效率,代码量也更小..本来就没必要递归来递归去的...

题目给了一段转化数据的代码段(是从输出的形式转化为输入的形式..)..虽然不能应用到程序里...但可以充分利用这个代码段来生成数据,检验自己的程序~~

我发现的问题就是...当前到达字典数的某个点..不仅要看这个点是否是病毒标记点..而且其fail不断上去有哪些是病毒标记点都要查询...我就因为这个WA了好久....后来想起利用题目中的代码段生成数据...立马找到错误了...

顺便提供一组数据吧:

Data:

7 YQ==  Yg== YWI= YWJj YWJjZA== YmNk Y2Q= 1 YWJjZA==

Ans:

7

Program:

#include#include#include#includeusing namespace std;struct node{ int virus,son[256],fail; }point[50000];int n,m,ans,h,turn[256],l,temp[80000];char ss[10000];int s[10000];queue myqueue;bool used[600];void change(){ int i,len,k,j,p; len=strlen(ss); l=0; for (i=0;i='A' && i<='Z') turn[i]=i-'A'; else if (i>='a' && i<='z') turn[i]=i-'a'+26; else if (i>='0' && i<='9') turn[i]=i-'0'+52; else if (i=='+') turn[i]=62; else turn[i]=63; } while (~scanf("%d",&n)) { m=0; point[0].virus=point[0].fail=0; memset(point[0].son,0,sizeof(point[0].son)); while (n--) { scanf("%s",ss); change(); k=0; for (i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。