## 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

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

9755
7554
0524

## 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'.

## 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 1i1<i2<...<ik<|p| and |ijij+1|>1 for all 1j<k.
2. swap pij and pij+1 for all 1jk.
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 (1n105,1mmin{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+m1 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