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 410

char 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;
}