岳阳市交通建设投资公司门户网站,免费服务器使用推荐,app开发软件怎么做,网站导航条怎么做效果目录 1. 实验内容及上机实验所用平台1.1 实验内容1.2 实验平台软件 2. 流程图3. 源代码4. 用例测试5. 实验总结 1. 实验内容及上机实验所用平台
1.1 实验内容
【问题描述】 给定两个字符串 s1 和 s2#xff0c;求最长的 s1 前缀 ss 使得 ss 为 s2 的最长后缀#xff0c;输出… 目录 1. 实验内容及上机实验所用平台1.1 实验内容1.2 实验平台软件 2. 流程图3. 源代码4. 用例测试5. 实验总结 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 iostream
#include string
using namespace std;void getnext(string t, int *next) { // 求合并串 t 的 next int j 0, k -1, len_t t.length();next[0] -1; // 第一个 next 默认为 -1while (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;
}4. 用例测试
in.txt 的测试用例如下
clinton
homerriemann
marjorieaaaa
aaaaaaaaababa
cdefababaworkhardwo
woabcdefgfedcba
althoughthisisthetruthfedcbaabcdefabcdefgabcdef
abcdefgabcdefsomeone
thisisaongsentenceselizabethlistenedinsilence,butwasnotconvinced.theirbehaviourattheassemblyhadnotbeencalculatedtopleaseingeneral;andwithmorequicknessofobservationandlesspliancyoftemperthanhersister,andwithajudgment,too,unassailedbyanyattentiontoherself,shewasverylittledisposedtoapprovethem.theywereinfactveryfineladies,notdeficientingoodhumourwhentheywerepleased,norinthepowerofbeingagreeablewheretheychoseit;butproudandconceited.theywereratherhandsome,hadbeeneducatedinoneofthefirstprivateseminariesintown,hadafortuneoftwentythousandpounds,wereinthehabitofspendingmorethantheyought,andofassociatingwithpeopleofrank;andwerethereforeineveryrespectentitledtothinkwellofthemselves,andmeanlyofothers.theywereofarespectablefamilyinthenorthofEngland;acircumstancemoredeeplyimpressedontheirmemoriesthanthattheirbrothersfortuneandtheirownhadbeenacquiredbytrade.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. 5. 实验总结
这道题目其实就是找串的 next 值只要将两个串合并来找就可以了。但是要注意的是 next 值最大的不一定是答案因为在合并后可能会使得前缀和后缀相同的长度多余两个串的其中一个的长度比如两个串的元素都一样。所以还要判断当 next 值多余给定串 s1 或者 s2 的长度后要进行回溯。
