shift-and/or 字符串匹配算法

(Updated: )
(7 mins to read)

shift-and

在串s中查找串t规定串s的长度为n，串t的长度为m，字符串下标从0开始bitset B[26];预处理字符集中每个字母在串t中的出现的位置，各用一个bitset表示。B[s[i]-‘a’]表示的是s串中i位置与t串中哪些位置可以匹配bitset D;在s中枚举位置i，D[j]=1仅当串t的前缀t[0…j]是串s的后缀s[i-j…i]当D[m-1]=1时表示一次匹配当枚举位置i+1，就要更新DD = (D<<1|1)&B[s[i+1]-‘a’];复杂度$O(\frac{nm}{32})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int shift_and()
{
  int n = strlen(s), m = strlen(t);
  for(int i=0; i<n; i++)
    B[s[i]-'A'].set(i);
  int cnt = 0;
  for(int i=0; i<m; i++)
  {
    D <<= 1; D.set(0);
    D &= B[t[i]-'A'];
    if(D[n-1]) cnt++;
  }
  return cnt;
}

shift-or

与shiftand的B和D含义都相反，B=0表示存在，D=0表示匹配，所以初始时B和D全为1，每次转移D = (D<<1|B[s[i]-‘a’])

在普通的字符串匹配中这两者的作用显然没有kmp强，复杂度劣势但是在可选字符匹配中很有用规定每个位置可以与多个字符相匹配，此时只要让这些字符的B的那个位置都置1即可

  • hdu 5972 输出的时候令s[n+1]=0,然后puts(s[i-n+1])，再还原s[n+1]。如果先记录匹配位置最后双重for会T
  • hdu 5716
  • 牛客多校2G题给定长度为n的数组a和长度为m的数组b，询问数组a中每一位都严格大于数组b的子段个数可以把这个问题当成一个可选字符匹配问题，对于每个a[i]可以与所有<=a[i]的b[j]相匹配。考虑预处理出bitset B[N]，表示a的每一位可以与b的哪些位相匹配，然后跑一遍shift-and即可。这样会MLE，随着a的增大，能够匹配的位置不断增加，所以本质不同的bitset只有m个，开成bitset B[M]即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
const int N = 1.5e5 + 5, M = 4e4 + 5;
int n, m, idx[N];
pii a[N], b[M];
bitset<M> B[M], D;
int main()
{
  scanf("%d%d", &n, &m);
  for(int i=1; i<=n; i++) scanf("%d", &a[i].fi), a[i].se = i;
  for(int i=1; i<=m; i++) scanf("%d", &b[i].fi), b[i].se = i;
  sort(a+1, a+n+1); sort(b+1, b+m+1);
  for(int i=1; i<=m; i++)
    B[i] = B[i-1], B[i].set(b[i].se);
  for(int i=1, j=1; i<=n; i++)
  {
    while(j<=m && a[i].fi>=b[j].fi) ++j;
    idx[a[i].se] = j-1;
  }
  int ans = 0;
  for(int i=1; i<=n; i++)
  {
    D <<= 1; D.set(1);
    D &= B[idx[i]];
    if(D[m]) ++ans;
  }
  printf("%d\n", ans);
  return 0;
}

考虑预处理bitset B[i]表示b数组中第i位可以与a数组中哪些位相匹配。然后用一个全1的bitsetD，当D[i]=1时表示a数组中以i下标起始的长度为m的子段可以与b数组相匹配。只要枚举b数组中的所有位置让D &= (B[i]>>(i-1))即可，如果B[i][j]=0，那么D[j-i+1]起始的子段就不可能与b数组相匹配，因为a[j]!=b[i]。以上方法也可以用于字符串匹配。在牛客多校这题中，利用该方法可以仅开一个bitset B，因为在这里b数组下标的枚举顺序是任意的，所以我们可以对b排序后再枚举，然后利用尺取实现B的滚动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
const int N = 1.5e5 + 5, M = 4e4 + 5;
int n, m, idx[N];
pii a[N], b[M];
bitset<N> B, D;
int main()
{
  scanf("%d%d", &n, &m);
  for(int i=1; i<=n; i++) scanf("%d", &a[i].fi), a[i].se = i;
  for(int i=1; i<=m; i++) scanf("%d", &b[i].fi), b[i].se = i;
  sort(a+1, a+n+1); sort(b+1, b+m+1);
  for(int i=1; i<=n-m+1; i++) D.set(i);
  for(int i=m, j=n; i; i--)
  {
    while(j && a[j].fi>=b[i].fi) B.set(a[j--].se);
    D &= (B>>(b[i].se-1));
  }
  printf("%d\n", (int)D.count());
  return 0;
}