字符串编码

字符串编码

day1里的T1。

字符串哈希+暴力。

对S,T这两个字符串进行哈希,令数字0...25表示小写字母a...z,设f[i][j]表示串S前i位的j字符的哈希值,g[i]表示串T的i字符的哈希值。那么对于一个从x起始的S的子串,若选中字符i,j,此子串与T匹配的充要条件是S[x+|T|-1][i]-S[x-1][i]=T[j]且S[x+|T|-1][j]-S[x-1][j]=T[i]。

在判断时只需枚举每个起始位置,枚举两个字符i,j,判断选中i,j能否使S的子串与T匹配即可。

时间复杂度


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


const int N = 200000 + 10, Size = 26, Mul = 2333;


unsigned long long s[N][Size], t[Size], pow;
int ans[N], n, m;


bool fuck(int );


int main(void)
{
    freopen("encoding.in", "r", stdin);
    freopen("encoding.out", "w", stdout);
   
    scanf("%d%d ", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < Size; ++j)
            s[i][j] = s[i - 1][j] * Mul;
        ++s[i][getchar() - 'a'];
    }
    scanf(" ");
    pow = 1;
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 0; j < Size; ++j)
            t[j] *= Mul;
        ++t[getchar() - 'a'];
        pow *= Mul;
    }
    for (int i = 0; i <= n - m; ++i)
        if (fuck(i))
            ans[++ans[0]] = i + 1;
    printf("%d\n", ans[0]);
    for (int i = 1; i <= ans[0]; ++i)
        printf("%d ", ans[i]);
   
    fclose(stdin);
    fclose(stdout);
   
    return 0;
}


inline bool fuck(int x)
{
    bool use[Size] = {0};
    for (int i = 0; i < Size; ++i)
        if (!use[i] && s[x + m][i] - s[x][i] * pow != t[i])
        {
            bool change = 0;
            for (int j = i + 1; j < Size && !change; ++j)
                if (!use[j] && s[x + m][i] - s[x][i] * pow == t[j] && s[x + m][j] - s[x][j] * pow == t[i])
                    use[i] = use[j] = change = 1;
            if (!change)
                return 0;
        }
    return 1;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注