相关链接
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5716
神犇题解:http://www.cnblogs.com/clrs97/p/5985648.html
解题报告
这货$KMP$是不可做的,于是考虑用$bitset$来优化暴力
定义$v[i][j]$为文本串第$i$位是否能匹配模式串第$j$位
定义$f[i][j]$为第$i$种字符能否匹配模式串第$j$位
那么$v[i][j] = v[i – 1][j – 1] \ and \ f[s[i]][j]$
然后数组第二维用$bitset$优化,时间复杂度:$O(\frac{nm}{64})$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 2000009; const int M = 600; const int SGZ = 100; char s[N], sgz[SGZ]; bitset<M> v, f[SGZ]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline int id(char c) { if ('0' <= c && c <= '9') { return c - '0' + 1; } else if ('a' <= c && c <= 'z') { return c - 'a' + 11; } else if ('A' <= c && c <= 'Z'){ return c - 'A' + 37; } else { return 0; } } int main() { while (gets(s + 1)) { int n = strlen(s + 1), m = read(); v.reset(); for (int i = 0; i < SGZ; i++) { f[i].reset(); } for (int i = 1; i <= m; i++) { int SGZ = read(); scanf("%s", sgz + 1); for (int j = 1; j <= SGZ; j++) { f[id(sgz[j])][i] = 1; } } bool CantMatch = 1; for (int i = 1; i <= n; i++) { v = (v << 1) & f[id(s[i])]; v[1] = f[id(s[i])][1]; if (v[m]) { printf("%d\n", i - m + 1); CantMatch = 0; } } if (CantMatch) { puts("NULL"); } getchar(); } return 0; }
—————————— UPD 2017.7.3 ———————————
这题的简单拓展:http://www.lydsy.com/JudgeOnline/problem.php?id=4924