Regular Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1589 Accepted Submission(s): 430
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 ai(1≤ai≤10),representing that the i-th position of regular expression has ai numbers to be selected.Next there are ai 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
题目链接：HDU 5972
不看题解不会写系列……很神奇的算法，只能理解一点。
注：下面的文字中的下标全部从$0$开始，且起始和结束都是闭区间。
- 对于主串$S$和模式串$T$，当$S$串处理完第$i$个字符后，对于某个位置$k(0 \le k \le lent-1)$，若$ans[k]==1$，那么说明$T_0…T_k==S_{i-k}…S_i$（结论1）。
- 显然$T_0…T_k$是$T$串的前缀，$S_{i-k}…S_i$是$S$串的前缀$S_0…S_{i}$的后缀。
- 那么当$ans[lent-1]==1$时，令$k=lent-1$，则有$T_0…T_{lent-1}==S_{i-(lent-1)}…S_i$（利用结论1），这个式子可以看出$T$串出现在$S$串中，且起始位置为$i-(lent-1)$。
既然知道起始位置，输出长度为$lent$的子串就可以了。当然这题似乎有一点卡输入，建议用输入外挂配合$gets()$输入，输出用$puts()$
代码：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
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1005;
const int M = 5e6 + 7;
char s[M];
bitset<N> bit[10], T; //bit[i][j]表示字符集中第i个字符可以出现在第j个位置
int Scan() //输入外挂
{
int res = 0, flag = 0;
char ch;
if ((ch = getchar()) == '-') flag = 1;
else if (ch >= '0' && ch <= '9') res = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9')
res = res * 10 + (ch - '0');
return flag ? -res : res;
}
int main(void)
{
int n, i, k, x;
char ch;
while (~scanf("%d", &n))
{
for (i = 0; i < 10; ++i)
bit[i].reset();
T.reset();
for (i = 0; i < n; ++i)
{
k = Scan();
for (int j = 0; j < k; ++j)
{
x = Scan();
bit[x].set(i);
}
}
gets(s);
for (i = 0; s[i]; ++i)
{
T = T << 1;
T[0] = 1;
T &= bit[s[i] - '0'];
if (T[n - 1])
{
ch = s[i + 1];
s[i + 1] = '\0';
puts(s + i - n + 1);
s[i + 1] = ch;
}
}
}
return 0;
}