首页 > 代码库 > HDU 5972 Regular Number（ShiftAnd+读入优化）
HDU 5972 Regular Number（ShiftAnd+读入优化）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5972
【题目大意】
给出一个字符串，找出其中所有的符合特定模式的子串位置，符合特定模式是指，该子串的长度为n，并且第i个字符需要在给定的字符集合Si中
【题解】
利用ShiftAnd匹配算法。
bt[i]表示字符i允许在哪些位置上出现，我们将匹配成功的位置保存在dp中，那么就可以用dp[i]=dp[i-1]<<1&bt[s[i]]来更新答案了
利用滚动数组和bitset可以来优化这样的运算，当一个位置的匹配在更新的过程中没有丢失，
即始终在特定模式中直到定长，那么这个位置就是成功匹配位，复杂度为O(nm/64)
由于输入的数据量庞大，因此需要读入和输出优化。
终于AC了，补上大连赛区的遗憾。
【代码】
#include <cstdio>#include <bitset>#include <cstring>using namespace std;const int M=1010,N=5000010,U=256;bitset<M> dp[2],bt[U];int n,m,x,id[U],cnt,l;char s[N];namespace fastIO{ #define BUF_SIZE 100000 #define OUT_SIZE 1000000 bool IOerror=0; inline char nc(){ static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; if(p1==pend){ p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); if (pend==p1){IOerror=1;return -1;} }return *p1++; } inline bool blank(char ch){return ch==‘ ‘||ch==‘\n‘||ch==‘\r‘||ch==‘\t‘;} inline int read(char *s){ char ch=nc(); for(;blank(ch);ch=nc()); if(IOerror)return 0; for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch; *s=0; return 1; } inline int RI(int &a){ char ch=nc(); a=0; for(;blank(ch);ch=nc()); if(IOerror)return 0; for(;!blank(ch)&&!IOerror;ch=nc())a=a*10+ch-‘0‘; return 1; } struct Ostream_fwrite{ char *buf,*p1,*pend; Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;} void out(char ch){ if (p1==pend){ fwrite(buf,1,BUF_SIZE,stdout);p1=buf; }*p1++=ch; } void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}} ~Ostream_fwrite(){flush();} }Ostream; inline void print(char x){Ostream.out(x);} inline void println(){Ostream.out(‘\n‘);} inline void flush(){Ostream.flush();} char Out[OUT_SIZE],*o=Out; inline void print1(char c){*o++=c;} inline void println1(){*o++=‘\n‘;} inline void flush1(){if (o!=Out){if (*(o-1)==‘\n‘)*--o=0;puts(Out);}} struct puts_write{ ~puts_write(){flush1();} }_puts;};void init(){ cnt=0; for(int i=‘0‘;i<=‘9‘;i++)id[i]=cnt++;}void ShiftAnd(int n,int m){ int cur=1,f=0; dp[0].reset(); dp[0].set(0); for(int i=1;i<=n;i++,cur^=1){ dp[cur]=dp[cur^1]<<1&bt[id[s[i]]]; dp[cur].set(0); if(dp[cur][m]){ for(int j=i-m+1;j<=i;j++)fastIO::print(s[j]); fastIO::println(); } }}int main(){ //freopen("demo.in","r",stdin); //freopen("demo.out","w",stdout); init(); while(fastIO::RI(m)){ for(int i=0;i<cnt;i++)bt[i].reset(); for(int i=1;i<=m;i++){ fastIO::RI(l); for(int j=1;j<=l;j++){ fastIO::RI(x); bt[x].set(i); } }fastIO::read(s+1); n=strlen(s+1); ShiftAnd(n,m); }return 0;}
HDU 5972 Regular Number（ShiftAnd+读入优化）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。