多校联赛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[i1]+dp[i3]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[i1]+dp[i3]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;
}

感谢大佬博客