分类：bitset优化

HDU 5972 Regular Number Bitset优化字符串匹配

http://acm.hdu.edu.cn/showproblem.php?pid=5972


Regular Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Using regular expression to define a numeric string is a very common thing. Generally, use the shape as follows:
(0|9|7) (5|6) (2) (4|5)
Above regular expression matches 4 digits:The first is one of 0,9 and 7. The second is one of 5 and 6. The third is 2. And the fourth is one of 4 and 5. The above regular expression can be successfully matched to 0525, but it cannot be matched to 9634.
Now,giving you a regular expression like the above formula,and a long string of numbers,please find out all the substrings of this long string that can be matched to the regular expression.

Input

It contains a set of test data.The first line is a positive integer N (1 ≤ N ≤ 1000),on behalf of the regular representation of the N bit string.In the next N lines,the first integer of the i-th line is $a_i(1 ≤a_i≤ 10)$,representing that the i-th position of regular expression has $a_i$ numbers to be selected.Next there are $a_i$ numeric characters. In the last line,there is a numeric string.The length of the string is not more than 5 * 10^6.

Output

Output all substrings that can be matched by the regular expression. Each substring occupies one line

Sample Input

4
3 0 9 7
2 5 7
2 2 5
2 4 5
09755420524

Sample Output

9755
7554
0524
 

Source
2016ACM/ICPC亚洲区大连站-重现赛（感谢大连海事大学）

题意

给一个长度为n的模式子串，子串的每个位置分别可以是一些数字，即一个位置可以被多个数字匹配。再给定一个母串，问子串可以在哪些位置和母串匹配，并且输出匹配成功后的所有子串。

思路

对每一个数字建立一个bitset，对于每一个数字i的bitset b[i]来说，如果允许他出现在子串的j位置，那么设置b[i][j]=1，否则b[i][j]=0。维护一个bitset ans,枚举母串的每一个位置i，先将ans向高位移一位，再将ans的最低位置1后与这个位置的数字对应的bitset相与。这样，如果ans[k]=1表示从这个位置开始往前的长度为k+1的串可以和子串的前缀进行匹配。当ans[n-1]的时候，说明从i-n+1位置开始的母串可以和子串匹配，这个时候输出即可。由于巨大的io，所以需要加上FastIO才能通过
C++
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 5;
bitset<1005> b[12];
char s[maxn];
struct FastIO
{
static const int S = maxn * 2;
int wpos;
char wbuf[S];
FastIO() : wpos(0) {}
inline int xchar()
{
static char buf[S];
static int len = 0, pos = 0;
if(pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if(pos == len) exit(0);
return buf[pos ++];
}
inline int xint()
{
int s = 1, c = xchar(), x = 0;
while(c <= 32) c = xchar();
if(c == '-') s = -1, c = xchar();
for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x * s;
}
inline void xstring(char *s)
{
int c = xchar();
while(c <= 32) c = xchar();
for(; c > 32; c = xchar()) * s++ = c;
*s = 0;
}
inline void wchar(int x)
{
if(wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos ++] = x;
}
~FastIO()
{
if(wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;
int main()
{
int n;
while(1)
{
n = io.xint();
for(int i = 0; i < 10; i++) b[i].reset();
for(int i = 0; i < n; i++)
{
int x = io.xint();
while(x--)
{
int y = io.xint();
b[y][i] = 1;
}
}
io.xstring(s);
bitset<1005> ans;
for(int i = 0; s[i]; i++)
{
ans <<= 1;
ans[0] = 1;
ans &= b[s[i] - '0'];
if(ans[n - 1])
{
for(int j = i - n + 1; j <= i; j++) io.wchar(s[j]);
io.wchar('\n');
}
}
}
return 0;
}

 

 

Codeforces 754E Dasha and cyclic table bitset优化矩阵匹配

http://codeforces.com/problemset/problem/754/E

E. Dasha and cyclic table

time limit per test

6 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Dasha is fond of challenging puzzles: Rubik's Cube 3 × 3 × 3, 4 × 4 × 4, 5 × 5 × 5 and so on. This time she has a cyclic table of size n × m, and each cell of the table contains a lowercase English letter. Each cell has coordinates (i, j) (0 ≤ i < n, 0 ≤ j < m). The table is cyclic means that to the right of cell (i, j) there is the cell , and to the down there is the cell .

Dasha has a pattern as well. A pattern is a non-cyclic table of size r × c. Each cell is either a lowercase English letter or a question mark. Each cell has coordinates (i, j) (0 ≤ i < r, 0 ≤ j < c).

The goal of the puzzle is to find all the appearance positions of the pattern in the cyclic table.

We say that the cell (i, j) of cyclic table is an appearance position, if for every pair (x, y) such that 0 ≤ x < r and 0 ≤ y < c one of the following conditions holds:

  • There is a question mark in the cell (x, y) of the pattern, or
  • The cell of the cyclic table equals to the cell (x, y) of the pattern.

Dasha solved this puzzle in no time, as well as all the others she ever tried. Can you solve it?.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 400) — the cyclic table sizes.

Each of the next n lines contains a string of m lowercase English characters — the description of the cyclic table.

The next line contains two integers r and c (1 ≤ r, c ≤ 400) — the sizes of the pattern.

Each of the next r lines contains a string of c lowercase English letter and/or characters '?' — the description of the pattern.

Output

Print n lines. Each of the n lines should contain m characters. Each of the characters should equal '0' or '1'.

The j-th character of the i-th (0-indexed) line should be equal to '1', in case the cell (i, j) is an appearance position, otherwise it should be equal to '0'.

Examples

Input

C++
1
2
3
4
5
6
7
8
9
10
5 7
qcezchs
hhedywq
wikywqy
qckrqzt
bqexcxz
3 2
??
yw
?q

Output

C++
1
2
3
4
5
0000100
0001001
0000000
0000000
0000000

Input

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
10 10
fwtoayylhw
yyaryyjawr
ywrdzwhscy
hnsyyxiphn
bnjwzyyjvo
kkjgseenwn
gvmiflpcsy
lxvkwrobwu
wyybbcocyy
yysijsvqry
2 2
??
yy

Output

C++
1
2
3
4
5
6
7
8
9
10
1000100000
0000000001
0001000000
0000010000
0000000000
0000000000
0000000000
0100000010
1000000001
0000010000

Input

C++
1
2
3
4
5
6
7
8
9
10
11
8 6
ibrgxl
xqdcsg
okbcgi
tvpetc
xgxxig
igghzo
lmlaza
gpswzv
1 4
gx??

Output

C++
1
2
3
4
5
6
7
8
000100
000001
000000
000000
010001
000000
000000
000000

题意：

给定一个n*m的字母矩阵，这个矩阵在x和y方向都周期性延拓。在给定一个r*c的矩阵，其中?代表通配符。输出一个n*m的01矩阵，代表r*c的矩阵可以和n*m的矩阵在这个位置匹配上。

思路：

对于每一个1，是以这个点为左上角的r*c的矩阵的每一个格子是否匹配的逻辑与。用G[c][i][j]表示n*m矩阵的(i,j)位置是否是c，换句话说，如果G[c][i][j]=1，表示c可以在(i,j)位置可以和n*m的矩阵匹配上。将最后一个压成bitset。枚举r*c矩阵的每一个格子，再枚举这个格子出现n*m矩阵的哪一排。然后将G[rc[i][j]][i]怼到bitset ans[x-i]上面，表示这一排和rc[i][j]的匹配情况。最后将ans输出即可。

C++
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
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
const int maxn = 405;
bitset<maxn> G[26][maxn];
bitset<maxn> ans[maxn];
char buf[maxn];
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
{
ans[i].set();
scanf("%s", buf);
for(int j = 0; j < m; j++) G[buf[j] - 'a'][i][j] = 1;
}
int r, c;
scanf("%d %d", &r, &c);
for(int i = 0; i < r; i++)
{
scanf("%s", buf);
for(int j = 0; j < c; j++)
{
if(buf[j] == '?') continue;
int ch = buf[j] - 'a';
for(int k = 0; k < n; k++)
{
int x = (k - i) % n;
if(x < 0) x += n;
ans[x] &= (G[ch][k] >> j % m) | (G[ch][k] << m - j % m);
}
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
if(ans[i][j]) putchar('1');
else putchar('0');
putchar('\n');
}
return 0;
}

 

HDU 5745 La Vie en rose 手写bitset优化DP

http://acm.hdu.edu.cn/showproblem.php?pid=5745

La Vie en rose

Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description
Professor Zhang would like to solve the multiple pattern matching problem, but he only has only one pattern string p=p1p2...pm. So, he wants to generate as many as possible pattern strings from p using the following method:
1. select some indices i1,i2,...,ik such that 1≤i1<i2<...<ik<|p| and |ij−ij+1|>1 for all 1≤j<k.
2. swap pij and pij+1 for all 1≤j≤k.
Now, for a given a string s=s1s2...sn, Professor Zhang wants to find all occurrences of all the generated patterns in s.
 
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m (1≤n≤105,1≤m≤min{5000,n}) -- the length of s and p.
The second line contains the string s and the third line contains the string p. Both the strings consist of only lowercase English letters.
 
Output
For each test case, output a binary string of length n. The i-th character is "1" if and only if the substring sisi+1...si+m−1 is one of the generated patterns.
 

Sample Input

3

4 1

abac

a

4 2

aaaa

aa

9 3

abcbacacb

abc

 

Sample Output

1010

1110

100100100

 Author
zimpha
 Source
2016 Multi-University Training Contest 2
C++
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<cstdio>
#include <utility>
#include<stack>
using namespace std;
const int BLOCK_SIZE = 80;
struct MyBitset
{
    long long *p;
    MyBitset()
    {
        p = new long long [BLOCK_SIZE];
    }
    inline MyBitset(MyBitset &&x)
    {
        p = move(x.p);
        x.p = nullptr;
    }
    inline MyBitset & operator = (MyBitset &&x)
    {
        delete [] p;
        p = move(x.p);
        x.p = nullptr;
        return *this;
    }
    inline MyBitset & operator = (MyBitset &x)
    {
        if(p == nullptr) p = new long long [BLOCK_SIZE];
        for(int i = 0; i < 79; i++) p[i] = x.p[i];
        return *this;
    }
    inline void set(int pos)
    {
        int block = pos >> 6;
        pos &= 63;
        p[block] |= 1LL << pos;
    }
    inline bool get(int pos)
    {
        int block = pos >> 6;
        pos &= 63;
        return bool (p[block] & (1LL << pos));
    }
    inline MyBitset rsh()
    {
        MyBitset res;
        for(int i = 0; i <= 78; i++)
        {
            res.p[i] = p[i] >> 1;
            if(p[i + 1] & 1) res.p[i] |= 1LL << 63;
        }
        res.p[79] = p[79] >> 1;
        return res;
    }
    inline MyBitset lsh()
    {
        MyBitset res;
        for(int i = 79; i > 0; i--)
        {
            res.p[i] = p[i] << 1;
            if(p[i - 1] & (1LL << 63)) res.p[i] |= 1;
        }
        res.p[0] = p[0] << 1;
        return res;
    }
    inline MyBitset  operator & (const MyBitset &x) const
    {
        MyBitset res;
        for(int i = 0; i < 80; i++) res.p[i] = p[i] & x.p[i];
        return res;
    }
    inline MyBitset  operator | (const MyBitset &x) const
    {
        MyBitset res;
        for(int i = 0; i < 80; i++) res.p[i] = p[i] | x.p[i];
        return res;
    }
    inline void reset()
    {
        for(int i = 0; i < 80; i++) p[i] = 0;
    }
    ~MyBitset()
    {
        delete [] p;
    }
};
char s[100005];
char ans[100005];
char p[5005];
int main()
{
    MyBitset dp[3], tmp[3], L[26], R[26], D[26];
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, m;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++) ans[i] = '0';
        ans[n] = 0;
        scanf("%s %s", s, p);
        for(int i = 0; i < 3; i++) dp[i].reset();
        for(int i = 0; i < 26; i++) D[i].reset();
        for(int i = 0; i < m; i++) D[p[i] - 'a'].set(i);
        for(int i = 0; i < 26; i++)
        {
            R[i] = D[i].rsh();
            L[i] = D[i].lsh();
        }
        for(int i = 0; i < n; i++)
        {
            int idx = s[i] - 'a';
            auto &&tmp = (dp[0] | dp[1]).lsh();
            tmp.set(0);
            dp[0] = dp[2].lsh() & L[idx];
            dp[1] = tmp & D[idx];
            dp[2] = tmp & R[idx];
            if(dp[1].get(m - 1) || dp[0].get(m - 1)) ans[i - m + 1] = '1';
        }
        printf("%s\n", ans);
    }
    return 0;
}