【数据结构与算法——C语言】“串操作与算法”之“找出最长串及其长度”

1. 实验内容及上机实验所用平台

1.1 实验内容

【问题描述】
给定两个字符串 s1 和 s2，求最长的 s1 前缀 ss 使得 ss 为 s2 的最长后缀，输出该字符串和其长度。
【输入形式】
输入的每个测试用例由两行构成，第一行为 s1，第二行为 s2。你可以假设所有字母都为小写字母。
【输出形式】
每个测试用例的输出由单行组成，其中包含最长的字符串，该字符串是 s1 的前缀和 s2 的后缀，后面跟着该前缀的长度。如果最长的此类字符串是空字符串，则输出应为 0。s1 和 s2 的长度最多为 50000。
【样例输入】
aaariemann
marjorieaaa
【样例输出】
aaa 3
【样例说明】
输入的第一行字符串s1=‘aaariemann’，第二行字符串s2=‘marjorieaaa’。s1的前缀和s2的后缀最长相等字符串为aaa，因此输出aaa 3，而不是a 1。

1.2 实验平台软件

Dev-C++.

2. 流程图

3. 源代码

需要先在源代码目录下新建 in.txt 文件，在此文件下输入要测试的数据。

#include 
#include 
using namespace std;

void getnext(string t, int *next) {	// 求合并串 t 的 next 
	int j = 0, k = -1, len_t = t.length();
	next[0] = -1;	// 第一个 next 默认为 -1
	while (j < len_t) {
		if (k == -1 || t[j] == t[k]) {	// 若 k 为 -1 或者字符相同，j、k 后移 
			j++; k++;
			next[j] = k;
		}
		else k = next[k];	// 字符不同时，k 回退 
	}
}

int main() {
	freopen("in.txt", "r", stdin);
	string s, t;
	int i = 0, len_s, len_t, len;
	while (cin >> s >> t) {
		cout << "\t第2题 - 找出最长串及其长度\n\n";
		//cout << "--------------------------------------------------------------\n\n";
		printf("[%d] 样例输入：%s %s\n\n", ++i, s.c_str(), t.c_str());
		
		printf("[%d] 样例输出：", i);
		len_s = s.length();
		len_t = t.length();
		len = len_s + len_t;
		t = s + t;	// 合并两个串 
		int *next = new int[len + 1];
		getnext(t, next);	// 计算合并串 t 的 next 值 
		while (next[len] > len_s || next[len] > len_t) len = next[len];	// 最长串的长度不能超过给定两个串的任何一个的长度 

		if (next[len] != 0) {	// 若 next 值不为 0，则输出串 s1 的前缀及其长度 
			for (int j = 0; j < next[len]; j++) cout << s[j];
			cout << " " << next[len] << endl;
		}
		else cout << "0\n";	// 否则没有找到最长串，输出 0 
		cout << "\n\n==============================================================\n\n";
	}
	cout << "9个样例输出完毕！\n\n";
	freopen("CON", "r", stdin);	// 为了可直接查看exe可执行文件，需要将权限返回键盘 
	system("pause");
	return 0;
}
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

4. 用例测试

in.txt 的测试用例如下：

clinton
homer

riemann
marjorie

aaaa
aaaaaaaa

ababa
cdefababa

workhardwo
wo

abcdefgfedcba
althoughthisisthetruthfedcbaabcdef

abcdefgabcdef
abcdefgabcdef

someone
thisisaongsentences

elizabethlistenedinsilence,butwasnotconvinced.theirbehaviourattheassemblyhadnotbeencalculatedtopleaseingeneral;andwithmorequicknessofobservationandlesspliancyoftemperthanhersister,andwithajudgment,too,unassailedbyanyattentiontoherself,shewasverylittledisposedtoapprovethem.theywereinfactveryfineladies,notdeficientingoodhumourwhentheywerepleased,norinthepowerofbeingagreeablewheretheychoseit;butproudandconceited.theywereratherhandsome,hadbeeneducatedinoneofthefirstprivateseminariesintown,hadafortuneoftwentythousandpounds,wereinthehabitofspendingmorethantheyought,andofassociatingwithpeopleofrank;andwerethereforeineveryrespectentitledtothinkwellofthemselves,andmeanlyofothers.theywereofarespectablefamilyinthenorthofEngland;acircumstancemoredeeplyimpressedontheirmemoriesthanthattheirbrother'sfortuneandtheirownhadbeenacquiredbytrade.Mr.Bingleyinheritedpropertytotheamountofnearlyanhundredthousandpoundsfromhisfather,whohadintendedtopurchaseanestate,butdidnotlivetodoit.--mr.Bingleyintendeditlikewise,andsometimesmadechoiceofhiscounty;butashewasnowprovidedwithagoodhouseandthelibertyofamanor,itwasdoubtfultomanyofthosewhobestknewtheeasinessofhistemper,whetherhemightnotspendtheremainderofhisdaysatNetherfield,andleavethenextgenerationtopurchase.Hissisterswereveryanxiousforhishavinganestateofhisown;butthoughhewasnowestablishedonlyasatenant,missBingleywasbynomeansunwillingtopresideathistable,norwasmrs.Hurst,whohadmarriedamanofmorefashionthanfortune,lessdisposedtoconsiderhishouseasherhomewhenitsuitedher.mr.bingleyhadnotbeenofagetwoyears,whenhewastemptedbyanaccidentalrecommendationtolookatNetherfieldHouse.Hedidlookatitandintoitforhalfanhour,waspleasedwiththesituationandtheprincipalrooms,satisfiedwithwhattheownersaidinitspraise,andtookitimmediately.
thoughnodispositioncouldofferagreatercontrasttohisown,andthoughwithhisownheneverappeareddissatisfied.

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

5. 实验总结

这道题目其实就是找串的 next 值，只要将两个串合并来找就可以了。但是要注意的是 next 值最大的不一定是答案，因为在合并后，可能会使得前缀和后缀相同的长度多余两个串的其中一个的长度，比如两个串的元素都一样。所以还要判断当 next 值多余给定串 s1 或者 s2 的长度后，要进行回溯。