Post 2

Veröffentlicht am | Edited on

你的负担将变成礼物，你受的苦将照亮你的路。

「一本通 2.2 例 1」剪花布条

题目描述

原题来自：HDU 2087

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

输入格式

输入数据为多组数据，读取到 # 字符时结束。每组数据仅有一行，为由空格分开的花布条和小饰条。花布条和小饰条都是用可见 ASCII 字符表示的，不会超过 10001000 个字符。

注意：这个 # 应为单个字符。若某字符串开头有 #，不意味着读入结束！

输出格式

对于每组数据，输出一行一个整数，表示能从花纹布中剪出的最多小饰条个数。

样例

样例输入

1
2
3
abcde a3
aaaaaa aa
#

样例输出

1
2
0
3

数据范围与提示

对于全部数据，字符串长度 \leq 1000≤1000。

题解

挺简单的KMP的题。

至于保证不重叠也很简单，匹配成功一个的时候让匹配值=0即可，至于为什么保留前面一个忽略和当前冲突的就不用说了，很简单的贪心思想。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 10005
char s[maxn] , p[maxn];
int next[maxn] , ans;
int main()
{
	while(true)
	{
		scanf("%s",s+1);
		int sl = std::strlen(s+1);
		if(sl == 1 && s[1] == '#') break;
		ans = 0;
		scanf("%s",p+1);
		int now = 0 , pl = std::strlen(p+1);
		for(int i = 1 ; i < pl ; ++i){
			while(now > 0 && p[i + 1] != p[now + 1])	now = next[now];
			if(p[i + 1] == p[now + 1])	++now;
			next[i + 1] = now;
		}
		now = 0;
		for(int i = 0 ; i < sl ; ++i){
			while(now > 0 && s[i + 1] != p[now + 1])	now = next[now];
			if(s[i + 1] == p[now + 1])	++now;
			if(now == pl){
				++ans;
				now = 0;
			}
		}
		printf("%d\n",ans);
	}
}

一本通 2.1 练习 1」Power Strings

题目描述

原题来自：POJ 2406

给定若干个长度 \le 10^6≤106 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 则最多有 33 个 ab 连接而成。

输入格式

输入若干行，每行有一个字符串。特别的，字符串可能为 . 即一个半角句号，此时输入结束。

样例

样例输入

1
2
3
4
abcd
aaaa
ababab
.

样例输出

1
2
3
1
4
3

数据范围与提示

字符串长度

题解

有点难度的KMP题。对于一个由长度大于1的循环节k次循环组成的字符串，最大相同前后缀必定是k-1个循环节组成的。设循环节长度为L

必要性显然，也就是说最大相同前后缀长度不小于k-1个循环字符串。

考虑假设最大前缀多x位。显然x <= next(L)。

然而这意味着每一个字符向后移动x位依然相同，所以最小循环节是x，与最初假设矛盾。

因此答案是

注意检验

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 1000005
char s[maxn] , p[maxn];
int next[maxn] , n;
int main()
{
	while(scanf("%s",s+1))
	{
		if(s[1] == '.' && std::strlen(s+1) == 1)	break;
		int now = 0 , n = std::strlen(s + 1);
		for(int i = 1 ; i < n ; ++i)
		{
			while(now > 0 && s[i + 1] != s[now + 1])	now = next[now];
			if(s[i + 1] == s[now + 1])	++now;
			next[i + 1] = now;
		}
		int pl = 0;
		for(int i = n - next[n] + 1 ; i <= n ; ++i)
			p[++pl] = s[i];
		if(!pl)	{
			puts("1") ; continue;
		}
		now = 0;
		bool flag = true;
		for(int i = 1 ; i <= n ; ++i)
		{
			++now;
			if(s[i] != p[now])	flag = false;
			if(i % pl == 0)	now = 0;
		}
		if(flag)
			printf("%d\n",n / (n - next[n]));
		else printf("1\n");
	}
}

「一本通 2.2 练习 1」Radio Transmission

题目描述

原题来自：BalticOI 2009

给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行给出字符串的长度 LL，第二行给出一个字符串，全由小写字母组成。

输出格式

输出最短的长度。

样例

样例输入 1

1
2
8
cabcabca

样例输出 1

1
3

样例说明

对于样例，我们可以利用 abc 不断自我连接得到 abcabcabc，读入的 cabcabca 是它的子串。

数据范围与提示

对于全部数据，

题解

和上面的一样，从上题证明中我们能够发现最长相同前后缀长度为L，字符串长度为n

那么我们可以把字符串后L位视为前L位平移n-L位，这样的话就相当于循环节是n-L.(除去特殊情况)

本题同理，就像分块一样，字符串只有可能有两个不完整的循环节，位于头尾。

但是中间最少有一个完整的循环节，这样前面不完整和后面不完整可以与中间组合，然后n-next(n)

就是正好一个完整的串。

不怎么会证，画图证明

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define maxn 1000005
char s[maxn];
int n , next[maxn];
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	int now = 0;
	for(int i = 1 ; i < n ; ++i)
	{
		while(now > 0 && s[i + 1] != s[now + 1]) now = next[now];
		if(s[i + 1] == s[now + 1])	++now;
		next[i + 1] = now;	
	}
	printf("%d", n - next[n]);
}

「一本通 2.2 练习 4」Censoring

题目描述

原题来自：USACO 2015 Feb. Silver

给出两个字符串 S 和 T，每次从前往后找到 S 的一个子串 A=T 并将其删除，空缺位依次向前补齐，重复上述操作多次，直到 SS 串中不含 TT 串。输出最终的 S 串。

输入格式

第一行包含一个字符串 S，第二行包含一个字符串 T。

输出格式

输出处理后的 SS 串。

样例

样例输入

1
2
whatthemomooofun
moo

样例输出

1
whatthefun

数据范围与提示

对于全部数据，

，保证字符串中只出现小写字母。

题解

一道比较有意思的题。

我们只需要开一开脑洞，将母串每个位置成功匹配的数量记录下来，然后删除后跳回删除串的前一个位置，从

继续开始匹配就行了。

时间复杂度分析依然要用到摊还分析的策略：
由于回跳的前提是删除了母串中长度为m的模式串，那么跳后剩下的距离和普通KMP是一样的，所以时间复杂度不变

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define maxn 1000005
char p[maxn];
std::string s;
int next[maxn] , fail[maxn];
bool k[maxn];
int main()
{
	std::cin >> s;
	scanf("%s",p+1);
	int now = 0;
	int sl = s.length() , pl = std::strlen(p + 1);
	for(int i = 1 ; i < pl ; ++i)
	{
		while(now > 0 && p[now + 1] != p[i + 1])	now = next[now];
		if(p[now + 1] == p[i + 1])	++now;
		next[i + 1] = now;
	}
	now = 0;
	for(int i = 0 ; i < s.length() ; ++i)
	{
		while(now > 0 && s[i] != p[now + 1])	now = next[now];
		if(s[i] == p[now + 1])	++now;
		fail[i] = now;
		if(now == pl)
		{
			int fr = i - pl + 1;
			s.erase(fr , pl);
			i = fr - 1;
			now = fail[i];
		}
	}
	std::cout << s;
}

「一本通 2.2 练习 3」似乎在梦中见过的样子

原题来自：2014 年湖北省队互测 Week2

「Madoka，不要相信 QB！」伴随着 Homura 的失望地喊叫，Madoka 与 QB 签订了契约。

这是 Modoka 的一个噩梦，也同时是上个轮回中所发生的事。为了使这一次 Madoka 不再与 QB 签订契约，Homura 决定在刚到学校的第一天就解决 QB。然而，QB 也是有许多替身的（但在第八话中的剧情显示它也有可能是无限重生的），不过，意志坚定的 Homura 是不会放弃的——她决定消灭所有可能是 QB 的东西。现在，她已感受到附近的状态，并且把它转化为一个长度为 nn 的字符串交给了学 OI 的你。

现在你从她的话中知道，所有形似于 A+B+AA+B+A 的字串都是 QB 或它的替身，且 |A|\ge k,|B|\ge 1∣A∣≥k,∣B∣≥1 （位置不同其他性质相同的子串算不同子串，位置相同但拆分不同的子串算同一子串），然后你必须尽快告诉 Homura 这个答案——QB 以及它的替身的数量。

注：对于一个字符串 SS，|S|∣S∣ 表示 SS 的长度。

输入格式

第一行一个字符串 SS，第二行一个数 kk。

输出格式

仅一行一个数 \text{ans}ans，表示 QB 以及它的替身的数量。

样例

样例输入 1

1
2
aaaaa
1

样例输出 1

1
6

样例输入 2

1
2
abcabcabc
2

样例输出 2

1
8

数据范围与提示

对于全部数据，1\le |S|\le 1.5\times 10^4,1\le k\le 1001≤∣S∣≤1.5×104,1≤k≤100，且字符集为所有小写字母。

题解

果然胡策题质量不高。。一道标算复杂度爆炸的题。。。最坏

居然过了。。

Code：

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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 15005
#define maxk 105
char s[maxn] , p[maxn];
int k , next[maxn] , ans;
int main()
{
	scanf("%s",s+1);
	scanf("%d",&k);
	int n = std::strlen(s + 1);
	for(int j = 1 ; j <= n ; ++j)
	{
		std::memset(next,0,sizeof(next));
		int len = 0;
		for(int i = j; i <= n ; ++i)
			p[++len] = s[i];
		for(int i = 1 , now = 0 ; i < len ; ++i)
		{
			while(now > 0 && p[i + 1] != p[now + 1])	now = next[now];
			if(p[i + 1] == p[now + 1])	++now;
			next[i + 1] = now;
			for(int t = next[i + 1] ; t >= k ; t = next[t])
				if((t << 1) <= i){
					++ans;
					break;
				}
		}
	}
	printf("%d",ans);
}

「一本通 2.2 练习 2」OKR-Periods of Words

原题来自：POI 2006

串是有限个小写字符的序列，特别的，一个空序列也可以是一个串。一个串 PP 是串 AA 的前缀，当且仅当存在串 BB，使得 A = PBA=PB。如果 P \not =AP̸=A 并且 PP 不是一个空串，那么我们说 PP 是 AA 的一个 proper 前缀。

定义 QQ 是 AA 的周期，当且仅当 QQ 是 AA 的一个 proper 前缀并且 AA 是 QQQQ 的前缀（不一定要是 proper 前缀）。比如串 abab 和 ababab 都是串 abababa 的周期。串 AA 的最大周期就是它最长的一个周期或者是一个空串（当 AA 没有周期的时候），比如说，ababab 的最大周期是 abab。串 abc 的最大周期是空串。

给出一个串，求出它所有前缀的最大周期长度之和。

输入格式

第一行一个整数 kk，表示串的长度。

接下来一行表示给出的串。

输出格式

输出一个整数表示它所有前缀的最大周期长度之和。

样例

样例输入

1
2
8
babababa

样例输出

1
24

数据范围与提示

对于全部数据，1\lt k\lt 10^61<k<106。

题解

想的挺对，不过不知道一开始有个傻逼细节写错了。。。

简述题意就是对于每个1~i，我们都要求出一个最大前缀（不能一模一样），使得这个前缀倍长后当前的1~i是其前缀（可以一样）。

还是用到KMP中next数组的一个性质来求循环节，上面说过是n-next(n),但是我们希望它最大，于是多跳几次next只要它大于0，并且最后必须保证

就可以加到答案里。

注意倍增优化。

时间复杂度：

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1000005
char s[maxn];
int next[21][maxn] , n ;
long long ans;
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i = 1 , now = 0 ; i < n ; ++i)
	{
		while(now > 0 && s[i + 1] != s[now + 1]) now = next[0][now];
		if(s[i + 1] == s[now + 1])	++now;
		next[0][i + 1] = now;
		for(int j = 1 ; j <= 20 ; ++j)
			next[j][i + 1] = next[j-1][next[j-1][i + 1]];
		int cur = next[0][i + 1];
		for(int j = 20 ; ~j ; --j)
			if(next[j][cur])
				cur = next[j][cur];
		if(next[0][cur])	cur = next[0][cur];
		if(!cur)	continue;
		if(((i + 1 - cur) << 1) >= i + 1)	ans += i + 1 - cur;
	}
	printf("%lld",ans);
	
}

这样一来一本通上的6道题目就全做完了，全部独立AC，还算不错。

鼓捣一下blog