Description

很久很久以前,在你刚刚学习字符串匹配的时候,有两个仅包含小写字母的字符串A和B,其中A串长度为m,B串长度为n。可当你现在再次碰到这两个串时,这两个串已经老化了,每个串都有不同程度的残缺。
你想对这两个串重新进行匹配,其中A为模板串,那么现在问题来了,请回答,对于B的每一个位置i,从这个位置开始连续m个字符形成的子串是否可能与A串完全匹配?

Input

第一行包含两个正整数m,n(1<=m<=n<=300000),分别表示A串和B串的长度。
第二行为一个长度为m的字符串A。
第三行为一个长度为n的字符串B。
两个串均仅由小写字母和*号组成,其中*号表示相应位置已经残缺。

Output

第一行包含一个整数k,表示B串中可以完全匹配A串的位置个数。
若k>0,则第二行输出k个正整数,从小到大依次输出每个可以匹配的开头位置(下标从1开始)。

Sample Input

3 7
a*b
aebr*ob

Sample Output

2
1 5

HINT

 

Source

By Claris

Solution

对于每个字母的权值就设为1~26。*的权值设为0。两个字符可以匹配当且仅当A_i∗B_j∗(A_i−B_j )^2等于0。那么我们将这个式子展开,展开以后的每一项分别用FFT计算即可。

 #include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring> #define R register
#define maxn 1048576
typedef long double db;
const db pi = acosl(-);
char A[maxn], B[maxn];
struct Complex {
db x, y;
inline Complex operator - (const Complex &that) const {return (Complex) {x - that.x, y - that.y};}
inline Complex operator * (const Complex &that) const {return (Complex) {x * that.x - y * that.y, x * that.y + y * that.x};}
inline void operator += (const Complex &that) {x += that.x; y += that.y;}
} w[maxn];
int N;
void init()
{
R int h = N >> ;
for (R int i = ; i < h; ++i) w[i + h] = (Complex) {cos( * pi / N * i), sin( * pi / N * i)};
for (R int i = h; i--; ) w[i] = w[i << ];
}
void bit_reverse(R Complex *a, R Complex *b)
{
for (R int i = ; i < N; ++i) b[i] = a[i];
for (R int i = , j = ; i < N; ++i)
{
i > j ? std::swap(b[i], b[j]), : ;
for (R int l = N >> ; (j ^= l) < l; l >>= );
}
}
void dft(R Complex *a)
{
for (R int l = , m = ; m != N; l <<= , m <<= )
for (R int i = ; i < N; i += l)
for (R int j = ; j < m; ++j)
{
R Complex tmp = a[i + j + m] * w[j + m];
a[i + j + m] = a[i + j] - tmp;
a[i + j] += tmp;
}
}
Complex a[maxn], b[maxn], ta[maxn], tb[maxn], tc[maxn], ans[maxn];
int aa[maxn], bb[maxn];
int main()
{
R int la, lb;
scanf("%s%s", A, B);
la = strlen(A); lb = strlen(B);
for (N = ; N < (la + lb); N <<= );
init();
std::reverse(A, A + la);
for (R int i = ; i < la; ++i) A[i] == '*' ? : aa[i] = A[i] - 'a' + ;
for (R int i = ; i < lb; ++i) B[i] == '*' ? : bb[i] = B[i] - 'a' + ; for (R int i = ; i < la; ++i) a[i].x = aa[i] * aa[i] * aa[i], a[i].y = ;
for (R int i = ; i < lb; ++i) b[i].x = bb[i], b[i].y = ;
bit_reverse(a, ta); bit_reverse(b, tb);
dft(ta); dft(tb);
for (R int i = ; i < N; ++i) ans[i] += (ta[i] * tb[i]); for (R int i = ; i < la; ++i) a[i].x = - * aa[i] * aa[i], a[i].y = ;
for (R int i = ; i < lb; ++i) b[i].x = bb[i] * bb[i], b[i].y = ;
bit_reverse(a, ta); bit_reverse(b, tb);
dft(ta); dft(tb);
for (R int i = ; i < N; ++i) ans[i] += (ta[i] * tb[i]); for (R int i = ; i < la; ++i) a[i].x = aa[i], a[i].y = ;
for (R int i = ; i < lb; ++i) b[i].x = bb[i] * bb[i] * bb[i], b[i].y = ;
bit_reverse(a, ta); bit_reverse(b, tb);
dft(ta); dft(tb);
for (R int i = ; i < N; ++i) ans[i] += (ta[i] * tb[i]); std::reverse(ans + , ans + N);
bit_reverse(ans, tc);
dft(tc);
// for (R int i = 0; i < N; ++i) printf("%lf %lf\n", tc[i].x, tc[i].y);
for (R int i = la - ; i < lb; ++i) if (fabs(tc[i].x / N) < 0.5) printf("%d ", i - la + );
return ;
}
/*
399906 399924 399942 399960 399978 399996
*/

FFT

其实这题的数据用bitset是可以水过的。不过可以卡。然后我优化了一发常数就只是最慢的数据本机3s以内了。我把代码放在这里欢迎大家来hack!  O(∩_∩)O~~

 #include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm> #define R register
#define maxn 500010
#define maxs 15635
//#define inline
char A[maxn], B[maxn];
/*inline bool eq(R char a, R char b)
{
return a == b || a == '*' || b == '*';
}*/
typedef unsigned uint;
int len; #define set(v, x) (v[x >> 5] |= 1u << (x & 31))
#define query(v, x) ((1u << (x & 31)) & v[x >> 5])
uint p[][][maxs];
uint aph[][maxs], ans[maxs];
inline void init(R int c)
{
R uint *t = p[c][], *tt;
for (R int i = ; i <= len; ++i) t[i] = aph[c][i];
for (R int i = ; i < ; ++i)
{
t = p[c][i]; tt = p[c][i - ];
for (R int j = ; j <= len; ++j)
t[j] = ((tt[j] >> ) | ((tt[j + ] & 1u) << ));
}
}
int cnt;
inline void bit_and(R int c, R int l)
{
R int fir = l >> ; R uint *t = p[c][l & ];
R int i = fir, j = ;
for (; i + < len; i += , j += )
{
ans[j] &= t[i];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
ans[j + ] &= t[i + ];
}
for (; i <= len; ++i, ++j) ans[j] &= t[i];
} //std::bitset<maxn> aph[26], ans;
int fail[maxn];
int r[maxn];
inline bool cmp(R int a, R int b) {return A[a] < A[b] || (A[a] == A[b] && (a & ) < (b & ));}
int main()
{
// freopen("str.in", "r", stdin);
// freopen("str.out", "w", stdout);
scanf("%s%s", A, B);
R int la = strlen(A), lb = strlen(B);
len = lb >> ;
R int xcnt = ;
for (R int i = ; i < la; ++i) xcnt += A[i] == '*';
for (R int i = ; i < lb; ++i) xcnt += B[i] == '*';
/*if (!xcnt)
{
fail[1] = 0;
for (R int i = la; i; --i) A[i] = A[i - 1];
for (R int i = lb; i; --i) B[i] = B[i - 1];
for (R int i = 2, p = 0; i <= la; ++i)
{
while (p && A[p + 1] != A[i]) p = fail[p];
A[p + 1] == A[i] ? ++p : 0;
fail[i] = p;
}
for (R int i = 1, p = 0; i <= lb; ++i)
{
while (p && A[p + 1] != B[i]) p = fail[p];
A[p + 1] == B[i] ? ++p : 0;
if (p == la)
{
printf("%d ", i - la + 1);
p = fail[p];
}
}
puts("");
return 0;
}*/
for (R int i = ; i < lb; ++i)
{
if (B[i] != '*') set(aph[B[i] - 'a'], i);
else for (R int j = ; j < ; ++j) set(aph[j], i);
set(ans, i);
}
for (R int i = ; i < ; ++i) init(i);
// fprintf(stderr, "%d %d\n", '*', 'a');
for (R int i = ; i < la; ++i) r[i] = i;
std::sort(r, r + la, cmp);
for (R int i = ; i < la; ++i)
if (A[r[i]] != '*')
bit_and(A[r[i]] - 'a', r[i]);
// ans &= (aph[A[i] - 'a'] >> i);
for (R int i = ; i + la - < lb; ++i) if (query(ans, i)) printf("%d ", i + ); puts("");
return ;
}

bitset

最新文章

  1. Docker如何为企业产生价值?
  2. [html]兼容 IE6 IE7 的简单网页框架
  3. c# File 操作
  4. shell中读写mysql数据库
  5. hbs
  6. js实现键盘操作对div的移动或改变-------Day43
  7. 《CS:APP》 chapter 8 Exceptional Control Flow 注意事项
  8. webpack 将不同类型的文件输出到不同文件夹
  9. 摹客iDoc 新功能“柔性工作流”,让设计随需而动
  10. RNQOJ 21 FBI数
  11. php的TS和NTS的区别
  12. poj1149构图题
  13. 【Redis学习之四】Redis数据类型 string
  14. django F表达式、Q表达式、annotate、order_by
  15. 全局最小割StoerWagner算法详解
  16. VMware下的Centos7联网并设置固定IP
  17. MathType公式波浪线怎么编辑
  18. vim资源帖
  19. 概述XML
  20. dota2交换物品

热门文章

  1. Linux的桌面环境gnome、kde、xfce、lxde 等等使用比较
  2. Linux软链接硬链接的区别
  3. python-day37(正式学习)
  4. mysql 相关文章
  5. ABCD 谁是小偷
  6. private修饰的方法可以通过反射访问,那么private的意义是什么?
  7. echarts-迁徙图地点图标颜色修改
  8. jquery事件绑定方式总结(补充)
  9. leetcode240 搜索二维矩阵 II
  10. Redhat 7修改主机名