多校联赛5补题

, ,
~~菜到自闭~~，还好有你在。。。
2019-08-05

1 string matching

只会暴力Tle

知识点：

  • 扩展KMP
  • Z-algorithm字符串匹配

KMP算法

假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？
朴素的匹配算法，或者说暴力匹配法，就是将两个字符串从头比到尾，若是有一个不同，那么从下一位再开始比。这样太慢了。所以KMP算法的思想是，对匹配串本身先做一个处理，得到一个next数组。这个数组是做什么用的呢？next [j] = k，代表j之前的字符串中有最大长度为k 的相同前缀后缀。记录这个有什么用呢？对于ABCDABC这个串，如果我们匹配ABCDABTBCDABC这个长串，当匹配到第7个字符T的时候就不匹配了,我们就不用直接移到B开始再比一次，而是直接移到第5位来比较，岂不美哉？所以求出了next数组，KMP就完成了一大半。next数组也可以说是开始比较的位数。
计算next数组的方法是对于长度为n的匹配串，从0到n-1位依次求出前缀后缀最大匹配长度。

模板：

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>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n, k, len1, len2;
int next1[1000001];
char s1[1000001];
char s2[1000001];
inline void get_next() //求出next数组
{
    //next数组是从 S[0到i-1]前子串 的前缀后缀最大值
    int t1 = 0, t2;
    next1[0] = t2 = -1;
    while(t1 < len2)
        if(t2 == -1 || s2[t1] == s2[t2]) //类似于KMP的匹配
            next1[++t1] = ++t2;
        else t2 = next1[t2]; //失配
}
inline void KMP() //KMP
{
    int t1 = 0, t2 = 0; //从0位开始匹配
    while(t1 < len1) //临界值
    {
        if(t2 == -1 || s1[t1] == s2[t2]) //匹配成功，继续
            t1++, t2++;
        else t2 = next1[t2]; //失配
        if(t2 == len2) printf("%d\n", t1 - len2 + 1), t2 = next1[t2]; //t2==lenn2时，匹配成功；t1-len2+1即为第一个字母的位置
    } //匹配成功后，t2置为next[t2]
}

int KMP_Count(char x[], int m, char y[], int n) //x 是模式串，y 是主串
{
    int i, j;
    int ans = 0;
    i = j = 0;
    while(i < n)
    {
        while(-1 != j && y[i] != x[j])j = next1[j];
        i++;
        j++;
        if(j >= m)
        {
            ans++;
            j = next1[j];
        }
    }
    return ans;
}

int main()
{
    scanf("%s", s1);
    scanf("%s", s2);
    len1 = strlen(s1);
    len2 = strlen(s2);
    get_next();
    KMP();
    cout << KMP_Count(s2, len2, s1, len1);
    for(int i = 1; i <= len2; ++i)
        printf("%d ", next1[i]); //输出next数组
    return 0;
}

扩展KMP

定义母串S，和字串T，设S的长度为n，T的长度为m，求T与S的每一个后缀的最长公共前缀，也就是说，设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀，要求出所有extendi。

扩展KMP的详细理解

扩展KMP求的是对于原串S1的每一个后缀子串与模式串S2的最长公共前缀。它有一个next[]数组和一个extend[]数组。

next[i]表示为模式串S2中以i为起点的后缀字符串和模式串S2的最长公共前缀长度.

其中，next[0]=l2;

next[i]=max{ k|i<=i+k-1<l2 &&S2.substring(i,i+k-1) == S2.substring(0,k-1) }

其中str.substring(i, j)表示str从位置i到位置j的子串，如果i>j则,substring为空。

extend[i]表示为以字符串S1中以i为起点的后缀字符串和模式串S2的最长公共前缀长度.

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
#include <iostream>
#include <string>

using namespace std;

/* 求解 T 中 next[]，注释参考 GetExtend() */
void GetNext(string & T, int & m, int next[])
{
    int a = 0, p = 0;
    next[0] = m;

    for (int i = 1; i < m; i++)
    {
        if (i >= p || i + next[i - a] >= p)
        {
            if (i >= p)
                p = i;

            while (p < m && T[p] == T[p - i])
                p++;

            next[i] = p - i;
            a = i;
        }
        else
            next[i] = next[i - a];
    }
}

/* 求解 extend[] */
void GetExtend(string & S, int & n, string & T, int & m, int extend[], int next[])
{
    int a = 0, p = 0;
    GetNext(T, m, next);

    for (int i = 0; i < n; i++)
    {
        if (i >= p || i + next[i - a] >= p) // i >= p 的作用：举个典型例子，S 和 T 无一字符相同
        {
            if (i >= p)
                p = i;

            while (p < n && p - i < m && S[p] == T[p - i])
                p++;

            extend[i] = p - i;
            a = i;
        }
        else
            extend[i] = next[i - a];
    }
}

int main()
{
    int next[100];
    int extend[100];
    string S, T;
    int n, m;
    
    while (cin >> S >> T)
    {
        n = S.size();
        m = T.size();
        GetExtend(S, n, T, m, extend, next);

        // 打印 next
        cout << "next:   ";
        for (int i = 0; i < m; i++)
            cout << next[i] << " ";
 
        // 打印 extend
        cout << "\nextend: ";
        for (int i = 0; i < n; i++)
            cout << extend[i] << " ";

        cout << endl << endl;
    }
    return 0;
}

Z-algorithm字符串匹配

Z-algorithm是用于字符串匹配。定义z[i]表示以i开头的子串和原串的最长公共前缀。我们通过线性时间计算出整个串的z数组，从而进行一些字符串的相关操作，该算法等价于扩展KMP。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void get_z()
{
    int l=0,r=0;
    for (int i=1;i<n;i++)
    {
        if (i>r)
        {
            l=i,r=i;
            while (r<n && s[r-l]==s[r]) r++;
            z[i]=r-l,r--;
        }
        else
        {
            int k=i-l;
            if (z[k]<r-i+1) z[i]=z[k];
            else
            {
                l=i;
                while (r<n && s[r-l]==s[r]) r++;
                z[i]=r-l,r--;
            }
        }
    } 
}

代码：

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
/*************************************************************************
 > FileName:
 > Author:      huangchangsheng
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;                             //int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1e6 + 5;
int n;
ll t, ans = 0;
ll z[maxn];
char s[maxn];
void get_z()
{
    int l=0,r=0;
    for (int i=1;i<n;i++)
    {
        if (i>r)
        {
            l=i,r=i;
            while (r<n && s[r-l]==s[r]) r++;
            r==n?z[i]+=r-l-1,r--:z[i]+=r-l,r--;
        }
        else
        {
            int k=i-l;
            if (z[k]<r-i+1) z[i]=z[k];
            else
            {
                l=i;
                while (r<n && s[r-l]==s[r]) r++;
                r==n?z[i]+=r-l-1,r--:z[i]+=r-l,r--;
                
            }
        }
        ans += z[i];
    } 
}
int main()
{
    cin >> t;
    while(t--)
    {
        memset(z,0,sizeof(z));
        ans = 0;
        scanf("%s", s);
        n = strlen(s);
        get_z();
        cout << ans + n - 1<<endl;
    }
    return 0;
}

2 permutation 2

思路：

分情况，当y == x+1，如果x == 1||y == n，则结果为1，否则为0
其他情况就用公式dp[i]=dp[i−1]+dp[i−3]dp[i] = dp[i - 1] + dp[i - 3];
鄙人愚钝，想了好久才搞清楚是怎么推得的

假设某一位(非两端)为ai，
1.若下一位为ai+1ai+1则继续往下讨论即可
2.若下一位为ai+2ai+2，则ai+1ai+1,ai+3ai+3
所以有ai,ai+1,ai+2,ai+3ai,ai+1,ai+2,ai+3然后就可以考虑下一轮
ai,ai+2,ai+1,ai+3,ai+4,ai+6,ai+5,ai+7ai,ai+2,ai+1,ai+3,ai+4,ai+6,ai+5,ai+7
可知dp[i]=dp[i−1]+dp[i−3]dp[i] = dp[i-1] + dp[i - 3]

代码：

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll mod = 998244353;

ll n,x,y;
ll a[100005];
void fun(){
    for(ll i=4;i<=100000;i++)
    {
        a[i]=(a[i-1]+a[i-3])%mod;
    }
}
    
int main()
{
    int t;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    a[1]=1;a[2]=1;a[3]=1;
    fun();
    cin>>t;
    while(t--)
    {
        cin>>n>>x>>y;
        if(x==1&&y==n) cout<<a[n]<<endl;
        else if(x==1) cout<<a[y-1]<<endl;
        else if(y==n) cout<<a[n-x]<<endl;
        else cout<<a[y-x-1]<<endl;
    }
    return 0;
 }

感谢大佬博客

3 permutation 1

思路：

想到查询1e4，而全排列是n!的增长，又8!=40320[5]，所以当n > 8时，显然n,1,2,3…
所以可以讨论后八位即可。

cmp函数的骚操作：

1
2
3
4
5
6
bool cmp(node a, node b)
{
    for (int i = 1; i < a.len; i++)
        if (a.f[i] - a.f[i - 1] != b.f[i] - b.f[i - 1])
            return a.f[i] - a.f[i - 1] < b.f[i] - b.f[i - 1];
}

代码：

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
/*************************************************************************
 > FileName:
 > Author:      huangchangsheng
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cmath>
#include <sstream>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;                             //int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 25;
int a[maxn], t, count1 = 0, k, n;
struct node
{
    int f[25];
    int len;
}No[500005];

bool cmp(node a, node b)
{
    for (int i = 1; i < a.len; i++)
        if (a.f[i] - a.f[i - 1] != b.f[i] - b.f[i - 1])
            return a.f[i] - a.f[i - 1] < b.f[i] - b.f[i - 1];
}

ll read()
{
    ll x = 0,f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main()
{
    t = read();
    while(t--)
    {
        n = read();
        k = read();
        int pos = 0;
        if (n < 9)
        {
            for (int i = 0; i < n; i++)
                a[i] = i + 1;
            do
            {
                pos++;
                for (int i = 0; i < n; i++)
                    No[pos].f[i] = a[i];
            }while(next_permutation(a,a + n));
        }
        else
        {
            for (int i = 0, j = 8; i < 8; i++, j--)
                a[i] = n - j;

            do
            {
                pos++;
                No[pos].f[0] = n;
                for (int i = 1; i < n - 8; i++)
                    No[pos].f[i] = i;
                for (int i = n - 8, j = 0; i < n; i++, j++)
                    No[pos].f[i] = a[j];
            }while(next_permutation(a, a + 8));
        }
        for (int i = 1; i <= pos; i++)
            No[i].len = n;
        sort(No + 1, No + pos + 1, cmp);
        for (int i = 0; i < n; i++)
            printf(i < n - 1?"%d ":"%d\n", No[k].f[i]);
    }
    return 0;
}

感谢大佬博客