题意
在串中找哪些地方出现了。中有通配字符。
设第一个串的长度为,第二个串的长度为。下标从开始。
首先我们把串中的位置的值设为。然后构造
显然只有当且仅当时,在中位置开头的长度为的串能够与串匹配。
展开得到
把反向就是
前面两个项是卷积形式FFT就行了,最后一项加起来是定值。
所以就可以做了。
另外一道题bzoj 4259: 残缺的字符串是一样的做法。只是里也有通配字符,那么再多乘一个就行了。
CODE
#include
using namespace std;
const int MAXN = 1const double Pi = acos(-1.);
typedef long double LD;
typedef long long LL;
struct cp {
LD x, y;
cp(){x=y=0;}
cp(LD x, LD y):x(x), y(y){}
inline cp operator +(const cp &o)const { return cp(x+o.x, y+o.y); }
inline cp operator -(const cp &o)const { return cp(x-o.x, y-o.y); }
inline cp operator *(const cp &o)const { return cp(x*o.x-y*o.y, x*o.y+y*o.x); }
}f[MAXN], g[MAXN];
char a[MAXN], b[MAXN];
int len, n, m, rev[MAXN]; LL ans[MAXN];
inline void init(int N) {
for(len = 1; len for(int i = 0; i >1]>>1)|((len>>1)*(i&1));
}
inline void DFT(cp *arr, int flg) {
for(int i = 0; i for(int i = 2; i cp wn = cp(cos(2*Pi/i), flg*sin(2*Pi/i));
for(int j = 0; j cp w = cp(1, 0);
for(int k = j; k cp x = arr[k], y = w * arr[k + i/2];
arr[k] = x + y;
arr[k + i/2] = x - y;
}
}
}
if(!~flg) for(int i = 0; i }
int main () {
scanf("%s%s", a, b);
n = strlen(a);
m = strlen(b);
init(n+m);
LL sum = 0;
for(int i = 0; i b[i] = b[i] == '?' ? 0 : b[i],
sum += b[i]*b[i]*b[i];
for(int i = 0; i for(int i = 0; i DFT(f, 1), DFT(g, 1);
for(int i = 0; i DFT(f, -1);
for(int i = m-1; i
memset(f, 0, sizeof f); for(int i = 0; i memset(g, 0, sizeof g); for(int i = 0; i DFT(f, 1), DFT(g, 1);
for(int i = 0; i DFT(f, -1);
for(int i = m-1; i
int cnt = 0;
for(int i = 0; i if(ans[i] + sum == 0) ++cnt;
printf("%dn", cnt);
for(int i = 0; i if(ans[i] + sum == 0) printf("%dn", i);
}