Blackops

初心易得，始终难守

0%

HDU 5716 带可选字符的多字符串匹配（shift-and匹配算法）

发表于 分类于 ， ，

带可选字符的多字符串匹配

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 818 Accepted Submission(s): 194

Problem Description
有一个文本串，它的长度为m(1≤m≤2000000)，现在想找出其中所有的符合特定模式的子串位置。

符合特定模式是指，该子串的长度为n(1≤n≤500)，并且第i个字符需要在给定的字符集合Si中。

因此，描述这一特定模式，共需要S1,S2,…,Sn这n个字符集合。每个集合的大小都在1∼62之间，其中的字符只为数字或大小写字母。

Input
第一行为一个字符串，表示待匹配的文本串。注意文本串中可能含有数字和大小写字母之外的字符。

第二行为一个整数n。

以下n行，分别描述n个字符集合。每行开始是一个1∼62之间的整数，随后有一个空格，接下来有一个字符串表示对应字符集合的内容。整数表示字符集合的大小，因此它也就是字符串的长度。输入保证字符串中的字符只为数字或大小写字母且没有重复。（注：本题有多组测试数据）

Output
每当从某个位置开头的，长度为n的子串符合输入的模式，就输出一行，其中包含一个整数，为它在文本串的起始位置。位置编号从1开始。

如果文本串没有任何位置符合输入模式，则最后输出一个字符串”NULL”，占一行。

Sample Input
aaaabacabcabd
3
3 abc
2 bc
3 abc

Sample Output
4
6
8
9

题目链接：HDU 5716
跟HDU 5972非常像，虽然在加了输入输出外挂之后解决了超时的问题，但是开始$WA$了，然后发现题目中的主串中的字符不一定是字符集里的字符，因此感觉应该有两种解决办法

  1. 把给定字符集之外的字符映射到独立出来的$id$上，这样最多只用$|字符集|+1$个字符。
  2. 结合一下shift-and匹配的性质，当$ans[k]==1$说明$T_0…T_k==S_{i-k}…S_i$，注意这里的$S_i$是作为前缀的后缀的最后一位，既然是非空后缀，那么最后一位总是不会变的，然后考虑$S[i]$为非给定字符集内的字符的情况，它此时作为最后一位会使得$S[i]$无法和任意的字符匹配，那么$S$中以$i$结尾的前缀的后缀均无法与任何字符匹配，因此要把当前记录的结果清零。然后就可以做了。

第一种代码：

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;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 2000010;
const int M = 505;
char S[N], T[M];
int id[256];
bitset<M>bit[63], ans;

void init()
{
    for (int i = 0; i <= 63; ++i)
        bit[i].reset();
    ans.reset();
}
void Out(int a)      //输出外挂
{
    if (a < 0)
    {
        putchar('-');
        a = -a;
    }
    if (a >= 10)
        Out(a / 10);
    putchar(a % 10 + '0');
}
int main(void)
{
    int idx = 0, i, j, n, m, len;
    for (i = 0; i < 256; ++i)
        id[i] = 62;
    for (i = '0'; i <= '9'; ++i)
        id[i] = idx++;
    for (i = 'a'; i <= 'z'; ++i)
        id[i] = idx++;
    for (i = 'A'; i <= 'Z'; ++i)
        id[i] = idx++;
    while (gets(S) != NULL)
    {
        init();
        m = strlen(S);
        scanf("%d", &n);
        for (i = 0; i < n; ++i)
        {
            scanf(" %d %s", &len, T);
            for (j = 0; j < len; ++j)
                bit[id[T[j]]][i] = 1;
        }
        int tot = 0;
        for (i = 0; i < m; ++i)
        {
            ans <<= 1;
            ans[0] = 1;
            ans &= bit[id[S[i]]];
            if (ans[n - 1])
            {
                Out(i - n + 1 + 1);
                putchar('\n');
                tot = 1;
            }
        }
        if (!tot)
            puts("NULL");
        getchar();
    }
    return 0;
}

第二种代码：

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;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 2000010;
const int M = 505;
char S[N], T[M];
int id[256];
bitset<M>bit[62], ans;

void init()
{
    for (int i = 0; i < 62; ++i)
        bit[i].reset();
    ans.reset();
}
void Out(int a)      //输出外挂
{
    if (a >= 10)
        Out(a / 10);
    putchar(a % 10 + '0');
}
int main(void)
{
    int idx = 0, i, j, n, m, len;
    for (i = 0; i < 256; ++i)
        id[i] = -1;
    for (i = '0'; i <= '9'; ++i)
        id[i] = idx++;
    for (i = 'a'; i <= 'z'; ++i)
        id[i] = idx++;
    for (i = 'A'; i <= 'Z'; ++i)
        id[i] = idx++;
    while (gets(S))
    {
        init();
        m = strlen(S);
        scanf("%d", &n);
        for (i = 0; i < n; ++i)
        {
            scanf(" %d %s", &len, T);
            for (j = 0; j < len; ++j)
                bit[id[T[j]]][i] = 1;
        }
        int tot = 0;
        for (i = 0; i < m; ++i)
        {
            ans <<= 1;
            ans[0] = 1;
            if (~id[S[i]])
            {
                ans &= bit[id[S[i]]];
                if (ans[n - 1])
                {
                    Out(i - n + 1 + 1);
                    putchar('\n');
                    tot = 1;
                }
            }
            else
                ans.reset();
        }
        if (!tot)
            puts("NULL");
        getchar();
    }
    return 0;
}