本机可过但是洛谷不过,前两个测试点答案都一样
查看原帖
本机可过但是洛谷不过,前两个测试点答案都一样
903039
muyuyumu楼主2024/3/21 19:37
#include <iostream>
#include <cstring>
using namespace std;
int usedWord[22];
int n = 0;
char word[22][40];
int length[22];
int maxLength=0;
char currentWord[100];
int Joint(char* goal, char* sources, int index, int currentLength);
void jielong(char* currentWord, int currentLength);
int FindTheSamePosition(char* goal, char* resouce, int goalLength, int startIndex);
//todo:
//FindTheSamePosition模块测试//完成
//一个单词中有两种可以对应的情况的判定
int main()
{
	cin >> n;
	cin.get();
	for (int i=0;i<n;i++)
	{
	  usedWord[i]=0;
		cin.getline(word[i], 20);
		length[i] = 0;
		while (true)
		{
			if (word[i][length[i]] == '\0')
			{
				break;
			}
			length[i]++;
		}
	}  
	cin >> currentWord[0];

	

	jielong(currentWord, 1);
	cout << maxLength;
	
}
void jielong(char* currentWord,int currentLength)
{
	for (int i = 0; i < n; i++)
	{
		if (usedWord[i] >= 2)
		{
			continue;
		}
		int startPosition = FindTheSamePosition(currentWord, word[i], currentLength, -1);
		//只需要找第一个符合的就可以,多个符合时必然第二个大
		if (startPosition != -1)
		{
			usedWord[i]++;
			int tempLegth = currentLength;
			currentLength=Joint(currentWord, word[i], startPosition, currentLength);
			maxLength=currentLength > maxLength ? currentLength : maxLength;
			jielong(currentWord, currentLength);
			//不用对currentWord进行回溯,当前递归层级的长度(currentLength)限制了在下一递归层级带来的字符数增加会被隐藏
			currentLength = tempLegth;
			usedWord[i]--;
		}
	}
	return;
}
/// <summary>
/// 完成字符的拼接,该模块调试正确
/// </summary>
/// <param name="goal">目标串</param>
/// <param name="sources">待拼接串</param>
/// <param name="index">标定待拼接串的位置</param>
/// <param name="currentLength">目标串的长度</param>
/// <returns></returns>
int Joint(char* goal, char* sources, int index,int currentLength)

{
	while (true)
	{
		goal[currentLength-1] = sources[index];
		currentLength++;
		index++;
		if (sources[index]=='\0')
		{
			return currentLength-1;
		}
	}
}
/// <summary>
/// 返还在原串中找到的位置
/// </summary>
/// <param name="goal"></param>
/// <param name="resouce"></param>
/// <param name="goalLength"></param>
/// <param name="startIndex">初始为-1,之后为上一次找到的字母的下一位</param>
/// <returns></returns>
int FindTheSamePosition(char* goal, char* resouce,int goalLength,int startIndex)
{
	if (goalLength == 1&&goal[0]==resouce[0])
	{
		return 0;
	}
	int tempIndex = goalLength - 1;
	int currentIndex = startIndex+1;
	//表示现在与目标串末位相同的位置
	while (true)
	{
		
		if (goal[tempIndex] == resouce[currentIndex])
		{
			
			int index = currentIndex;
			//用来向前搜索的变量
			while (true)
			{
				if (index == 0)
				{
					return currentIndex;
				}
				index--;
				tempIndex--;
				if (goal[tempIndex] != resouce[index])
				{
					tempIndex = goalLength - 1;
					break;
				}
				if (tempIndex == 0)
			    //第一位不用比较,相等则包含错误,不等则直接错误
				{
					return -1;
				}
				
			}
		}
		currentIndex ++;
		if (resouce[currentIndex+1] == '\0')
			//+1排除Resource最后一位与goal最后一位比较的情况
		{
			return -1;
		}
	}
}
2024/3/21 19:37
加载中...