xtu oj 连接字符串

回顾

• A+B III
• 问题 H: 三角数
• 问题 G: 3个数
• 等式 数组下标查询，降低时间复杂度
• 1405 问题 E: 世界杯
• xtu 数码串
• xtu oj 神经网络
• xtu oj 1167 逆序数（大数据）
• xtu oj 原根
• xtu oj 不定方程的正整数解
• xtu oj 最多的可变换字符串
• xtu oj String I
• xtu oj 字母序列
• xtu oj 分段
• xtu oj 完全平方数II

思路

• 这个首先就要注意输入的时候要加上 !=EOF
• 然后就是要找两个字符串的最长的公共子序列，要求是一个是在前面字符串的后面，另一个在后面字符串的前面，找到最长的重合的部分，然后把两个字符串拼接起来就是答案，最短的时候是两个字符串完全相等，就输出 a 字符串就好，最长的就是完全不等，就直接把两个字符串连接起来。
• 输入两个字符串， !=EOF 怎么加？
• 最大是两百，所以哪怕是 n^2 的时间复杂度也是可以接受的，所以应该直接暴力就行了。好像不是 n^2 ，而是 n^3 ，那就是 8*10^6 ，这个时间复杂度也是可以接受的。
• 题目好像没说两个字符串的长度是相等的，所以要用两个长度变量来分别表示字符串长度。
• 假设把前面字符串叫做 jjj ，后面字符串叫做 ttt ，一定要是 jjj 的后面的完整一块等于 ttt 的前面的完整一块。也就是说遍历的时候，一定要从开始相等的第一个字母开始，到 jjj 的最后一个元素，中间不能出现不相等的元素，在这个前提下，找一个 jjj 里面下标最小的元素，就好。（原来我最开始想到了这个，但是在代码里面没加这个判断，后面过不了才找到这个错误，感觉完全是运气，所以最好整理思路的时候把条件列出来，写代码的时候把条件限制得严格一些）
• 观察最后一个样例可以发现，两个字符串可以交换，也就是满足题目里面说的字典序的问题。字典序最小，这个时候等于说有两个条件，一个条件是拼接之后最短，另一个条件是字典序最小。那么我们可以写一个函数，实现两个字符串拼接之后最短，用两个数组存答案，等于说实现的这个函数的参数是两个字符串，这两个字符串先后顺序不一样，就会有不一样的答案，比较答案的长度，输出答案短的，长度相等就输出字典序小的。
• 比较字典序就是比较每一个字母的大小，反正是存到了数组里面，还是比较容易比较的，字符串拼接函数的一些参数我不是很熟悉，现在查一下。不然只能用数组模拟了。strncat 好像只能拼接字符串前面 n 个字符，所以假设我想从中间开始拼接，还是只能自己模拟一下。
• 比较两个字符串字典序可以直接用 strcmp 函数，strcmp(ans1,ans2) ，小于零表示 ans1 更小，但是这个函数不能直接比较两个字符串的长度，只能一个一个字母去比较，所以通俗地说，就是比较字典序的一个函数。
  
  哈哈哈，有点难写，有一些细节需要注意。
• 最后总结一下：这题思路比较直观，找公共的元素，代码细节比较多，一个是要求输出字典序小的，第二是前面字符串要枚举完最后一个元素才算满足条件，第三是两个字符串可能完全没有公共部分，需要特判。

代码

#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#define N 410char jjj[N];//分别存两个字符串
char ttt[N];char ans1[N];//存不同字典序的答案
char ans2[N];
void get_ans(char arr1[],char arr2[],char ans[]){int len1=strlen(arr1),len2=strlen(arr2);//字符串长度bool has_found=false;//特判两个字符串没有满足条件的部分，比如这种，abc,def 这种for(int i=0;i<len1;i++){//从第一个字符串前面开始枚举bool is_ok=true;int max_ans=0;//最多的相同的元素的个数bool arr1_out=false;//第一个字符串数组没有枚举到最后一个元素，我们要求第一个字符串数组枚举到了最后一个元素for(int j=i,k=0;j<len1&&k<len2;j++,k++){//注意这里的 j 和 k 是同步变化的if(j==len1-1){//假设能枚举完第一个字符串的最后一个元素，就说明满足条件arr1_out=true;}if(arr1[j]==arr2[k]){max_ans++;}else{//只要在枚举过程中出现一个不相等的元素，就结束枚举is_ok=false;break;}}if(is_ok&&arr1_out){//因为从前面开始找的，所以找到的第一个满足条件的就是最大的公共部分，就是答案strcpy(ans,arr1);//把字符串拼接好存到答案数组里面for(int hhh=len1,j=max_ans;j<len2;hhh++,j++){ans[hhh]=arr2[j];}has_found=true;break;}}if(has_found==false){//特判没有啥共同元素的情况，abc,def  这种情况strcpy(ans,arr1);//把 arr1 和 arr2 拼接起来复制到 ans 答案数组里面strcat(ans,arr2);}
}int main(){while(scanf("%s%s",jjj,ttt)!=EOF){//多样例输入get_ans(jjj,ttt,ans1);//得到两个答案数组get_ans(ttt,jjj,ans2);if(strlen(ans1)<strlen(ans2)){//比较长度printf("%s\n",ans1);}else if(strlen(ans1)>strlen(ans2)){printf("%s\n",ans2);}else{if(strcmp(ans1,ans2)<=0){//比较字典序printf("%s\n",ans1);}else{printf("%s\n",ans2);}}for(int i=0;i<N;i++){//清空数组ans1[i]='\0',ans2[i]='\0';}}return 0;
}