有一个文本串，它的长度为m (1 <= m <= 2000000)，现在想找出其中所有的符合特定模式的子串位置。
符合特定模式是指，该子串的长度为n (1 <= n <= 500)，并且第i个字符需要在给定的字符集合Si中。 因此，描述这一特定模式，共需要S1，S2，...，Sn这n个字符集合。每个集合的大小都在1~62之间，其中的字符只为数字或大小写字母。 Input 第一行为一个字符串，表示待匹配的文本串。注意文本串中可能含有数字和大小写字母之外的字符。 第二行为一个整数n。 以下n行，分别描述n个字符集合。每行开始是一个1~62之间的整数，随后有一个空格，接下来有一个字符串表示对应字符集合的内容。整数表示字符集合的大小，因此它也就是字符串的长度。输入保证字符串中的字符只为数字或大小写字母且没有重复。 Output 每当从某个位置开头的，长度为n的子串符合输入的模式，就输出一行，其中包含一个整数，为它在文本串的起始位置。位置编号从1开始。 如果文本串没有任何位置符合输入模式，则最后输出一个字符串"NULL"，占一行。
就是问B串在A串里出现的所有位置。和一般字符串匹配的区别是每个字符可以匹配若干个字符。
shift_and算法。
bool数组can[i][j]==TRUE表示A[i-j+1..i]能与B[1..j]匹配，match[ch][i]表示字符ch在不在B串第i个位置的集合里。
can[i][j]=can[i-1][j-1]&map[A[i]][j]
这玩意可以用bitset加速。。时间复杂度O(m*n/64)，
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxn=505; 7 int id[233]; 8 bitset can[233],now; 9 char s[2002333];10 int i,j,k,n,m;11 12 13 int ra,fh;char rx;14 inline int read(){15 rx=getchar(),ra=0,fh=1;16 while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();17 if(rx=='-')fh=-1,rx=getchar();18 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra*fh;19 }20 21 char ss[10];int len;22 inline void outx(int x){23 if(!x){putchar('0');return;}24 while(x)ss[++len]=x%10+48,x/=10;25 while(len)putchar(ss[len--]);26 }27 int main(){28 j=0;29 for(i='0';i<='9';i++)id[i]=++j;30 for(i='A';i<='Z';i++)id[i]=++j;31 for(i='a';i<='z';i++)id[i]=++j;32 33 int len=0;char ch=getchar();34 while(ch!='\n')s[++len]=ch,ch=getchar();35 n=read();36 for(i=1;i<=n;i++)for(j=read();j;j--)can[id[(int)getchar()]][i]=1;37 bool FLAG=0;38 for(i=1;i<=len;i++){39 now<<=1,now[1]=1,now&=can[id[s[i]]];40 if(now[n])/*outx(i-n+1),putchar('\n'),*/FLAG=1,printf("%d\n",i-n+1);41 }42 if(!FLAG)puts("NULL");43 }