数据结构与算法(二)字符串

1.合格的字符串

描述

     老师给小学生门布置了一些作业,让它们按照一个模版写一些字符串交上来,

同学们把作业交上来了,问题来了,这么多的作业老师批改不过来,现在请你帮老师

写一个程序,帮助老师确定各个字符串是否合格。

    首先老师有一个匹配模版,比如是“aa[123]bb”这一个字符串,同学们交的各种

作业字符串如aa1bb、aa2bb、aa3bb都算是正确匹配看,而aacbb就是错误的字符串。

(即待查字符串对应于模版方括号内的部分,应该为方括号内字符串的一个子字符)。

    我们需要做的就是按照模版,找出正确的字符串和所在的行。

输入

输入的第一行为一个整数n,表示有多少个学生的作业,即有多少行需要检查的字符串。(1<=n<=50)
中间为n行字符串,代表着n个学生们写的作业。每个字符串长度小于50。
最后一行为1行字符串,代表着老师给的匹配模板。

输出

输出合格的字符串的行号和该字符串。(中间以空格隔开)

样例输入

4
Aab
a2B
ab
ABB
a[a2b]b

样例输出

1 Aab
2 a2B
4 ABB

提示

被检测的字符串中只有数字和字母。

 

2.挤奶网格

描述

每天早上奶牛被挤奶的时候,农夫约翰的奶牛会成一个R行,C列的长方形网格(1 <= R <= 10,000,1 <= C <= 75)。据我们所知,约翰i研究奶牛行为上,是一个专家,同时也在编写一个关于如何饲养奶牛的书。他发现如果将每头奶牛用一个大写字母来标识其种类,在挤奶的时候他的奶牛所形成的二维模式似乎有时候是从一些更小的长方形模式重复得来。帮助 寻找最小面积的长方形单位,该长方形单位可以通过重复从而构成整个挤奶网格,注意到这个小的长方形单位的维度并不需要由整个挤奶网格的维度均分得到,具体可以参见示例。

输入

第一行: 两个以空格间隔的整数 R和C
第二行到第R+1行:牛形成的网格,每个格子以一个大写字母来表示每个奶牛的种类。这R行中每行包含C个中间没有间隔符的字母。

输出

一行,即网格形成所需要的最小单位的面积。

样例输入

2 5
ABABA
ABABA

样例输出

2

提示

整个挤奶网格可以从模式 ‘AB’重复得来。第一行和最后一行的A用模式‘AB’的前缀部分A得到。即求最小覆盖矩阵。

 

3.Seek the name, seek the fame

描述

The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm:

Step1. Connect the father’s name and the mother’s name, to a new string S.
Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).

Example: Father=’ala’, Mother=’la’, we have S = ‘ala’+’la’ = ‘alala’. Potential prefix-suffix strings of S are {‘a’, ‘ala’, ‘alala’}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)

输入

The input contains a number of test cases. Each test case occupies a single line that contains the string S described above.

Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.

输出

For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby’s name.

样例输入

ababcababababcabab
aaaaa

样例输出

2 4 9 18
1 2 3 4 5

提示

.

 

4.除去C程序中的注释

描述

C程序的注释用/*…*/来表示。请写一个程序,将输入的C程序源代码中的注释去掉,输出去掉注释之后的源代码。

用于测试的C代码保证符合语法,不使用C++的//注释语法。

注意,C语言不允许出现嵌套注释。具体来说,对于/*/**/”*/”,如果不允许嵌套注释,那么它表示字符串”*/”;如果允许嵌套注释,它表示一个引号”。

还请注意,字符串中出现的注释符/*属于字符串的一部分,注释中出现的双引号”属于注释的一部分。

输入

符合语法的C代码文本文件。代码每行不超过200个字符。

输出

去掉注释后的C代码。要求只能去掉注释,不可以做其他的修改,比如调整缩进,去除注释之外的换行符等。

样例输入

#include 
#include 
#include 

/*Hash Search: 
Hash function: division method; 
handling collisions: open addressing's linear probing. 
In this exercise, M is the basic area's length, all keys are non negative integers.*/

#define M 11

int hash(int key)
{
	return key % M;
}

void init_hash(int* hashtable)
{
	int i;
	for(i = 0; i < M; ++i)
	{
		hashtable[i] = -1;
	}
}

/*return value: 
1:found, *position is the key's index; 
0:not found, *position is where to insert the key; 
-1:overflow. */
int search_hash(int* hashtable, int key, int* position)
{
	int i, h = hash(key);
	for(i = 0; i < M; ++i)
	{
		if(key == hashtable[h])
		{
			*position = h;
			return 1;
		}
		if(-1 == hashtable[h])
		{
			*position = h;
			return 0;
		}
		h = (h+1) % M;
	}
	*position = -1;
	return -1;
}

/*return value: 1:inserted, 0:overflow*/
int insert_hash(int* hashtable, int key)
{
	int position, result;
	result = search_hash(hashtable, key, &position);
	if(-1 == result)
		return 0;
	hashtable[position] = key;
	return 1;
}

void main()
{
	int hashtable[M];
	init_hash(hashtable);
	srand(time(NULL));
	int i, j, key;
	for(i = 0; i < 8; ++i) 	/*make a hash table with 8 elements*/
	{
		key = rand() % 50;
		insert_hash(hashtable, key);
		printf("Insert %d\n", key);
		for(j = 0; j < M; ++j)
			printf("%3d", hashtable[j]);
		printf("\n");
	}

	printf("Please input the key to search:\n");
	scanf("%d", &key);
	i = search_hash(hashtable, key, &j);
	if(1 == i)
		printf("Found!Its index is %d\n", j);
	else
		printf("Not found!\n");
}

样例输出

#include 
#include 
#include 



#define M 11

int hash(int key)
{
	return key % M;
}

void init_hash(int* hashtable)
{
	int i;
	for(i = 0; i < M; ++i)
	{
		hashtable[i] = -1;
	}
}


int search_hash(int* hashtable, int key, int* position)
{
	int i, h = hash(key);
	for(i = 0; i < M; ++i)
	{
		if(key == hashtable[h])
		{
			*position = h;
			return 1;
		}
		if(-1 == hashtable[h])
		{
			*position = h;
			return 0;
		}
		h = (h+1) % M;
	}
	*position = -1;
	return -1;
}


int insert_hash(int* hashtable, int key)
{
	int position, result;
	result = search_hash(hashtable, key, &position);
	if(-1 == result)
		return 0;
	hashtable[position] = key;
	return 1;
}

void main()
{
	int hashtable[M];
	init_hash(hashtable);
	srand(time(NULL));
	int i, j, key;
	for(i = 0; i < 8; ++i) 	
	{
		key = rand() % 50;
		insert_hash(hashtable, key);
		printf("Insert %d\n", key);
		for(j = 0; j < M; ++j)
			printf("%3d", hashtable[j]);
		printf("\n");
	}

	printf("Please input the key to search:\n");
	scanf("%d", &key);
	i = search_hash(hashtable, key, &j);
	if(1 == i)
		printf("Found!Its index is %d\n", j);
	else
		printf("Not found!\n");
}

提示

注意字符串,字符,转义字符的情况。
看看自己有没有考虑
“a\”/*ccc*/”
这种情况。

 

5.全在其中

描述

你设计了一个新的加密技术,可以用一种聪明的方式在一个字符串的字符间插入随机的字符串从而对信息进行编码。由于专利问题,我们将不会详细讨论如何在原有信息中产生和插入字符串。不过,为了验证你的方法,有必要写一个程序来验证原来的信息是否全在最后的字符串之中。

给定两个字符串s和t,你需要判断s是否是t的“子列”。也就是说,如果你去掉t中的某些字符,剩下字符将连接而成为s。

 

输入

输入包括多个测试样例。每一个都是由空格分隔的由字母数字ASCII字符组成的两个特定的字符串s和t。s和t的长度不超过100000。

输出

对于每个测试样例,如果s是t的“子列”,则输出”Yes”,否则输出”No”

样例输入

sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter

样例输出

Yes
No
Yes
No

6.字符串乘方

描述

给定两个字符串a和b,我们定义a*b为他们的连接。例如,如果a=”abc” 而b=”def”, 则a*b=”abcdef”。 如果我们将连接考虑成乘法,一个非负整数的乘方将用一种通常的方式定义:a^0=””(空字符串),a^(n+1)=a*(a^n)。

输入

每一个测试样例是一行可打印的字符作为输入,用s表示。s的长度至少为1,且不会超过一百万。最后的测试样例后面将是一个点号作为一行。

输出

对于每一个s,你应该打印最大的n,使得存在一个a,让s=a^n

样例输入

abcd
aaaa
ababab
.

样例输出

1
4
3

提示

本问题输入量很大,请用scanf代替cin,从而避免超时。

 

7.英语数字转换器

描述

在这个问题中,将用英语给你一个或多个整数。你的任务是将这些数字转换成整型表示。数字范围从-999,999,999到999,999,999.下面是你的程序必须考虑的详尽的英语单词表:

negative, zero, one, two, three, four,five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen,fifteen, sixteen, seventeen, eighteen, nineteen, twenty, thirty, forty, fifty,sixty, seventy, eighty, ninety, hundred, thousand, million

 

输入

输入包括多个样例,注意:

1.负数前面有词negative

2.当能用thousand的时候,将不用hundred。例如1500将写为”one thousand five hundred”,而不是”fifteen hundred”.

输入将以一个空行结束

输出

输出将是每一个单独一行,每一个后面一个换行符

样例输入

six
negative seven hundred twenty nine
one million one hundred one
eight hundred fourteen thousand twenty two

样例输出

6
-729
1000101
814022

 

8.统计字符数

描述

判断一个由a-z这26个字符组成的字符串中哪个字符出现的次数最多

输入

第1行是测试数据的组数n,每组测试数据占1行,是一个由a-z这26个字符组成的字符串
每组测试数据之间有一个空行,每行数据不超过1000个字符且非空

输出

n行,每行输出对应一个输入。一行输出包括出现次数最多的字符和该字符出现的次数,中间是一个空格。
如果有多个字符出现的次数相同且最多,那么输出ascii码最小的那一个字符

样例输入

2
abbccc

adfadffasdf

样例输出

c 3
f 4

 

9.Caesar密码

描述

Julius Caesar 生活在充满危险和阴谋的年代。为了生存,他首次发明了密码,用于军队的消息传递。假设你是Caesar 军团中的一名军官,需要把Caesar 发送的消息破译出来、并提供给你的将军。消息加密的办法是:对消息原文中的每个字母,分别用该字母之后的第5个字母替换(例如:消息原文中的每个字母A都分别替换成字母F),其他字符不 变,并且消息原文的所有字母都是大写的。 

密码字母:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
原文字母:V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

输入

最多不超过100个数据集组成。每个数据集由3部分组成:
起始行:START 
密码消息:由1到200个字符组成一行,表示Caesar发出的一条消息
结束行:END 
在最后一个数据集之后,是另一行:ENDOFINPUT

输出

每个数据集对应一行,是Caesar 的原始消息。

样例输入

START
NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX
END
START
N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ
END
START
IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ
END
ENDOFINPUT

样例输出

IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES
I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME
DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE

 

10.古代密码

描述

古罗马帝国有一个拥有各种部门的强大政府组织。其中一个部门就是保密服务部门。为了保险起见,在省与省之间传递的重要文件中的大写字母是加密的。当时最流行的加密方法是替换和重新排列。

替换方法是将所有出现的字符替换成其它的字符。有些字符会替换成它自己。例如:替换规则可以是将’A’ 到 ‘Y’替换成它的下一个字符,将’Z’替换成 ‘A’,如果原词是 “VICTORIOUS” 则它变成 “WJDUPSJPVT”。

排列方法改变原来单词中字母的顺序。例如:将顺序<2, 8=””>应用到 “VICTORIOUS” 上,则得到”IVOTCIRSUO”。

人们很快意识到单独应用替换方法或排列方法加密,都是很不保险的。但是如果结合这两种方法,在当时就可以得到非常可靠的加密方法。所以,很多重要信息先使用替换方法加密,再将加密的结果用排列的方法加密。用两种方法结合就可以将”VICTORIOUS” 加密成”JWPUDJSTVP”。

考古学家最近在一个石台上发现了一些信息。初看起来它们毫无意义,所以有人设想它们可能是用替换和排列的方法被加密了。人们试着解读了石台上的密码,现在他们想检查解读的是否正确。他们需要一个计算机程序来验证,你的任务就是写这个验证程序。

输入

输入有两行。第一行是石台上的文字。文字中没有空格,并且只有大写英文字母。第二行是被解读出来的加密前的文字。第二行也是由大写英文字母构成的。
两行字符数目的长度都不超过100。

输出

如果第二行经过某种加密方法后可以产生第一行的信息,输出 “YES”,否则输出”NO”。

样例输入

JWPUDJSTVP
VICTORIOUS

样例输出

YES

 

11.前缀中的周期

描述

一个字符串的前缀是从第一个字符开始的连续若干个字符,例如”abaab”共有5个前缀,分别是a, ab, aba, abaa,  abaab。

 

我们希望知道一个N位字符串S的前缀是否具有循环节。换言之,对于每一个从头开始的长度为 i (i 大于1)的前缀,是否由重复出现的子串A组成,即 AAA…A (A重复出现K次,K 大于 1)。如果存在,请找出最短的循环节对应的K值(也就是这个前缀串的所有可能重复节中,最大的K值)。

输入

输入包括多组测试数据。每组测试数据包括两行。
第一行包括字符串S的长度N(2 <= N <= 1 000 000)。
第二行包括字符串S。
输入数据以只包括一个0的行作为结尾。

输出

对于每组测试数据,第一行输出 “Test case #“ 和测试数据的编号。
接下来的每一行,输出前缀长度i和重复测数K,中间用一个空格隔开。前缀长度需要升序排列。
在每组测试数据的最后输出一个空行。

样例输入

3
aaa
12
aabaabaabaab
0

样例输出

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4
  •  

版权声明:本文为yhjpku原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。