有一个文本串，它的长度为m(1≤m≤2000000)m(1≤m≤2000000)，现在想找出其中所有的符合特定模式的子串位置。 符合特定模式是指，该子串的长度为n(1≤n≤500)n(1≤n≤500)，并且第ii个字符需要在给定的字符集合SiSi中。 因此，描述这一特定模式，共需要S1,S2,…,SnS1,S2,…,Sn这nn个字符集合。每个集合的大小都在1∼621∼62之间，其中的字符只为数字或大小写字母。
Input
第一行为一个字符串，表示待匹配的文本串。注意文本串中可能含有数字和大小写字母之外的字符。 第二行为一个整数nn。 以下nn行，分别描述nn个字符集合。每行开始是一个1∼621∼62之间的整数，随后有一个空格，接下来有一个字符串表示对应字符集合的内容。整数表示字符集合的大小，因此它也就是字符串的长度。输入保证字符串中的字符只为数字或大小写字母且没有重复。（注：本题有多组测试数据）
Output
每当从某个位置开头的，长度为nn的子串符合输入的模式，就输出一行，其中包含一个整数，为它在文本串的起始位置。位置编号从11开始。 如果文本串没有任何位置符合输入模式，则最后输出一个字符串”NULL”，占一行。
Sample Input
aaaabacabcabd
3
3 abc
2 bc
3 abc
Sample Output
4
6
8
9 其实还是模式匹配不过 每个可以匹配的字符有多重选择。 这种问题可以用 ShiftAnd解决，并行的位运算
建议自己可以 琢磨下代码，可以通过输出中间量来尽量看懂代码，然后再去看分析，这样的话就可以找到重点 ，更加好理解。 讲的不错链接 代码 #include using namespace std; #define LL long long const int N = 2000000+11;// 目标串长度 const int M = 500+11; // 模式串长度 const int S = 256 ; // 字符集的大小 bitsetdp[2],bt[S]; int id[S],sz; // 重编序号 void init(){ sz=0; for(int i='a';i<='z';i++) id[i]=++sz; for(int i='A';i<='Z';i++) id[i]=++sz; for(int i='0';i<='9';i++) id[i]=++sz; } char s[N],t[65]; void ShiftAnd(int n,int m){ int cur=1,f=0; dp[0].reset(); dp[0][0]=1; for(int i=1;i<=n;i++,cur^=1){ dp[cur]=dp[cur^1]<<1 & bt[id[s[i]]] ; // 并行寻找 dp[cur][0]=1; if(dp[cur][m]) printf("%d ",i-m+(f=1)); // t(m) t(m-1) t(m-2)...t(1) 倒着找到了 模式串 } if(!f) puts("NULL"); } int main(){ init(); while(gets(s+1)){ for(int i=1;i<=sz;i++) bt[i].reset(); // 清空 int n,m; n=strlen(s+1); scanf("%d",&m); for(int i=1;i<=m;i++){ int len; scanf("%d %s",&len,t); for(int j=0;j1; // bt[id[t[j]]][i] 表示 字符t[j] 在i位置上可选到 } ShiftAnd(n,m); getchar(); } return 0; }