CUC-Spring-Training字符串基础算法
Primo Pan
  2022-05-04 19:04:28 2022-05-04 19:04  

A - Oulipo

纯纯KMP模板题，通过率100%，应该没有什么问题。每一次匹配到直接把答案+1就行了。

B - Reverse String

过这题的同学都是直接brute force的，自然没有什么问题，官方题解也是直接暴力过的。但是我们也可以使用hash或者z-algorithm优化dfs过程。比如dfs中向右匹配的过程可以用z算法找模式串和当前串的LCP（最长公共前缀），反之往左走可以把两个串倒过来求一次z。（哈希同理），可以大大优化时间复杂度，如果把数据范围调大，这些做法值得同学们思考一下。

丢个py代码给各位尝尝鲜 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
q = int(input())
for i in range(q):
	s = input()
	t = input()
	n = len(s)
	m = len(t)
	ans = False
	for i in range(n):
		for j in range(0, n - i):
			k = m - 1 - j
			if i + j < k:
				continue                                 
			l1 = i
			r = i + j
			l2 = r - k                                
			if s[l1:r+1] + s[l2:r][::-1] == t:
				ans = True	
	print('YES' if ans else 'NO')

C - 于是他错误的点名开始了

Trie裸题，其实标程就是下发文件夹中的Trie.cpp，没能理解Trie的同学可以仔细阅读代码加深理解。

如果不是字符串专场，或者说在正儿八经的比赛里遇到这种题，同学们也完全可以开一个map，来解决这道题目，STL的功能非常强大，本着不重复发明轮子的原则，希望同学们善于利用。

upd...谢谢同学提醒，下发的代码中Trie放错代码了，我的锅我的锅。 

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

const int N = 500010;

char s[60];
int n, m, ch[N][26], tag[N], tot = 1;

int main() {
  scanf("%d", &n);

  for (int i = 1; i <= n; ++i) {
    scanf("%s", s + 1);
    int u = 1;
    for (int j = 1; s[j]; ++j) {
      int c = s[j] - 'a';
      if (!ch[u][c])
        ch[u][c] =
            ++tot;  // 如果这个节点的子节点中没有这个字符，添加上并将该字符的节点号记录为++tot
      u = ch[u][c];  // 往更深一层搜索
    }
    tag[u] = 1;  // 最后一个字符为节点 u 的名字未被访问到记录为 1
  }

  scanf("%d", &m);

  while (m--) {
    scanf("%s", s + 1);
    int u = 1;
    for (int j = 1; s[j]; ++j) {
      int c = s[j] - 'a';
      u = ch[u][c];
      if (!u) break;  // 不存在对应字符的出边说明名字不存在
    }
    if (tag[u] == 1) {
      tag[u] = 2;  // 最后一个字符为节点 u 的名字已经被访问
      puts("OK");
    } else if (tag[u] == 2)  // 已经被访问，重复访问
      puts("REPEAT");
    else
      puts("WRONG");
  }

  return 0;
}

D - Password

题目意思是说找到一个非前缀且非后缀的substring，使得它的长度最长，且它等于与它长度相同的前缀和后缀。也就是说找到一个最长的前缀，使得它也是一个后缀，并且这个子串在字符串中间出现过。

KMP和Z-algorithm皆可。KMP的话直接从pi[n]入手，如果pi[n]所代表的前缀在字符串中某个非前缀/后缀的位置出现过，那么这就是可行解，这利用了pi[n]是当前"最长匹配前缀"的性质。

如果用z算法，也比较直观。 处理出z数组后，我们记录前i项的z的最大值 对于第i+1项，如果z[i+1]+i==len&&max[i]>=z[i+1],即从i+1开始能匹配到后缀,且前面存在一个相同的串，他所代表的串就是符合条件的.

KMP By 本场Rank1同学

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
#include<iostream>
#include<stdio.h>
#include<cstring> 
using namespace std;

char p[2000007];
int nnext[2000007];
int book[2000007];

void GetNext()
{
	memset(nnext,0,sizeof(nnext));
	int k = strlen(p);
    nnext[0]=-1;
    int i = 0;
	int j = -1;
    while(i<k)
    {
        if (j==-1||p[i]==p[j])
        {
            ++i;
            ++j;
            nnext[i] = j;
        }
        else
            j = nnext[j];
    }
	for(int i=0;i<k;++i)
	++book[nnext[i]];
}

int main()
{
	while(~scanf("%s",p))
	{
		GetNext();
		int len = strlen(p);
		int judge = 0;
		while(nnext[len]!=0)
		{
			if(book[nnext[len]])
			{
				for(int i=0;i<nnext[len];++i)
				printf("%c",p[i]);
				++judge;
				break;
			}
			len = nnext[len];
		}
		if(judge==0)
		printf("Just a legend");
		printf("\n");
	}
	return 0;
}

Z-algorithm:

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
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int z[1000010],n,m,r,l;
char b[1000010];
int maxn=0;
int main()
{
    scanf("%s",b);
    m=strlen(b);
    for (int i=1;i<=m;i++)
    {
        if (i>r)
        {
            int t=i,bg=0;
            while (b[t]==b[bg])
                t++,bg++;
            z[i]=bg;
            r=t-1;
            l=i;
        }
        else
        {
            if (z[i-l]<r-i+1) z[i]=z[i-l];
            else
            {
                int t=r+1,bg=r-i+1;
                while (b[t]==b[bg])
                    t++,bg++;
                z[i]=bg;
                r=t-1;
                l=i;
            }
        }
    }
    int nw=0;
    for (int i=1;i<m;i++)
    {
        if (i+z[i]==m&&nw>=z[i])
            maxn=max(maxn,z[i]);
        nw=max(nw,z[i]);
    }
    if (maxn==0) printf("Just a legend");
    for (int i=0;i<maxn;i++)
        printf("%c",b[i]);
}

E - Spy Syndrome 2

给你一个长度为N的文本串，这个文本串是由一堆 单词拆分开之后每个单词变小写并翻转的来的，现在给你这个长度为N的字符串，还给你他的原来的组成成分，你要还原这句话，其中有的单词可能是多余的。

其实还是字典树的裸题，不过既然它翻转过来了，我们就直接倒序建立字典树，倒序跑Trie匹配，最后再将单词倒序输出即可。

By 本场Rank2同学

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
#include<bits/stdc++.h>
using namespace std;
//既有单词建树、reverse原、break原、dfs、倒序output
const int maxn=1e5+5;
const int maxx=1e6+5;
int tr[maxx][30],num[maxx],n,m,tot,dp[maxn];
string s[maxn];
string a;
vector<int>v;
void build_trie(string& s,int No) {
	int p=0;
	for (auto &j : s) {
		int c;
		if(j>='a'&&j<='z')c=j-'a';
		else if(j>='A'&&j<='Z')c=j-'A';
		if(!tr[p][c]) tr[p][c] = ++tot;
		p=tr[p][c];
	}
	num[p]=No;
}
void find(int t){
	int p=0;
	for(int i=t;i<n;i++){
		int c=a[i]-'a';
		if(!tr[p][c])return;
		p=tr[p][c];
		if(num[p])dp[i+1]=num[p];//mark the position
	}
}
void dfs(int k=n){//corret the order
	if(!k)return;
	int tmp=s[dp[k]].size();
	v.push_back(dp[k]);
	dfs(k-tmp);
}
int main(){
	scanf("%d",&n);
	cin>>a;
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		cin>>s[i];
		build_trie(s[i],i); 
	}
	reverse(a.begin(),a.end());
	find(0);
	for(int i=1;i<=n;i++){
		if(!dp[i])continue;
		find(i);
	}
	dfs();
//	cout<<"ok"<<endl;
	for(auto &r:v)cout<<s[r]<<" ";
	cout<<endl;
  	return 0;	
}

F - Hash Killer II

很有意思的题目，要你出一个字符串卡掉单哈希。

考察生日攻击，关于生日攻击，知乎上有一个回答讲的很不错。 点我点我

这题用到一个结论，在n个数里随机选数，选了个数后，发生冲突的概率就极大。 这题的mod数是1e9+7，我们把n调成1e5（就是最大值）,l选一个排列组合后足够大的数（比如20），直接随机输出一个串，就满足条件了。 

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main() {
    srand(time(0));
    cout << 100000 << " " << 20 << endl;
    for (int i = 1; i <= 100000; i++)
        cout << (char)(rand() % 26 + 'a');
}

G - Test

给你三个字符串，找⼀个字符串(它的⼦串含有以上三个字符串)，输出此字符串的最小⻓度。

显然有种拼接顺序，我们直接暴力枚举一下拼接顺序。（next_permutation)。因为要求最小长度，我们自然希望拼接时能尽量把重叠部分合并。那我们自然就希望后一个串的前缀和前一个串的后缀能尽可能多地重叠！那么用KMP/Z拼接的思路就非常明确了。

一鱼两吃,Z-algorithm:

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
int f[maxn];
string S[4];
int ord[3]={0,1,2};
int ans=maxlongint;
//z-algorithm
inline string skr(string a,string b)
{
	string T=a+'$'+b;//merge a & b
	int n=a.length();
	int m=b.length();
	int Len=n+m+1;
	f[0]=Len;
	int j=1,k;
	for (int i=1;i<Len;i=k)
	{
		if (j<i) j=i;
		while (T[j-i]==T[j] && j<Len)
			j++;
		f[i]=j-i;
		k=i+1;
		while (k+f[k-i]<j) k++;
	}
	int Lim=m+1;
	for (int i=n+1;i<Len;i++)
	{
		if(f[i]==n)	return b;
		if (i+f[i]>=Len){
			Lim=min(Lim,i-n);break;
		}
	}
	string cur;
	cur=b.substr(0,Lim-1)+a;
	return cur;
}
//main
int main()
{
	cin>>S[0]>>S[1]>>S[2];
	do {
		ans=min(ans,(int)skr(skr(S[ord[0]],S[ord[1]]),S[ord[2]]).length());
	}while (next_permutation(ord,ord+3));
	//暴力枚举三个串链接的顺序
	cout<<ans<<endl;
	return 0;
}

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int f[maxn];
string S[4];
int ord[3]={0,1,2};
int ans=maxlongint;
inline string skr(string a,string b)
{
	string T=a+'$'+b;//merge a & b
	int n=a.length();
	int m=b.length();
	int Len=n+m+1;
	//int j=-1;
	f[0]=-1;
	int j=-1;
	for(int i=1;i<Len;i++)
		{
			while (j!=-1 && T[j+1]!=T[i])
					j=f[j];
			if(T[i]==T[j+1])
					j++;
			f[i]=j;
		}//找next数组
	for (int i=n+1;i<Len;i++)
		if (f[i]==n-1) return b;//a是b的子串
	string cur=b.substr(0,m-1-f[Len-1])+a;//b减去a的一部分前缀+a
	return cur;
}
//main
int main()
{
	
	cin>>S[0]>>S[1]>>S[2];
	do {
		ans=min(ans,(int)skr(skr(S[ord[0]],S[ord[1]]),S[ord[2]]).length());
	}while (next_permutation(ord,ord+3));
	//暴力枚举三个串链接的顺序
	cout<<ans<<endl;
	return 0;
}