文档章节

hdoj_1867A + B for you again

N3verL4nd
 N3verL4nd
发布于 2017/03/25 10:43
字数 596
阅读 1
收藏 0

A + B for you again

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2989    Accepted Submission(s): 730


Problem Description
Generally speaking, there are a lot of problems about strings processing. Now you encounter another such problem. If you get two strings, such as “asdf” and “sdfg”, the result of the addition between them is “asdfg”, for “sdf” is the tail substring of “asdf” and the head substring of the “sdfg” . However, the result comes as “asdfghjk”, when you have to add “asdf” and “ghjk” and guarantee the shortest string first, then the minimum lexicographic second, the same rules for other additions.
 

Input
For each case, there are two strings (the chars selected just form ‘a’ to ‘z’) for you, and each length of theirs won’t exceed 10^5 and won’t be empty.
 

Output
Print the ultimate string by the book.
 

Sample Input

   
asdf sdfg asdf ghjk
 

Sample Output

   
asdfg asdfghjk
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#pragma warning(disable : 4996)
int Next[100005];
void get_next(char *B, int m)
{
	char pat[100005] = {0};
	strcpy(pat + 1, B);
	Next[1] = 0;
	int i, j = 0;
	for(i = 2; i <= m; i++)
	{
		while(j > 0 && pat[j+1] != pat[i])
		{
			j = Next[j];
		}
		if(pat[j+1] == pat[i])
		{
			j += 1;
		}
		Next[i] = j;
	}
}
int kmp(char *A, char *B)
{
	char text[100005] = {0};
	char pat[100005] = {0};
	strcpy(text + 1, A);
	strcpy(pat + 1, B);
	int n = strlen(text + 1);
	int m = strlen(pat + 1);
	get_next(B, m);
	int i, j = 0;
	for(i = 1; i <= n; i++)
	{
		while(j > 0 && pat[j+1] != text[i])
		{
			j = Next[j];
		}
		if(pat[j+1] == text[i])
		{
			j += 1;
		}
		if(i == n)
		{
			return j;
		}
	}
	return 0;
}
int main()
{
	freopen("in.txt", "r", stdin);
	char text[100005], pat[100005];
	int x, y;
	while(scanf("%s%s", text + 1, pat + 1) != EOF)
	{
		x = kmp(text + 1, pat + 1);
		y = kmp(pat + 1, text + 1);
	//	cout << x << " " << y << endl;
		if(x == y)
		{
			if(strcmp(text + 1, pat + 1) > 0)
			{
				printf("%s", pat + 1);
				printf("%s\n", text + x + 1);
			}
			else if(strcmp(text + 1, pat + 1) < 0)
			{
				printf("%s", text + 1);
				printf("%s\n", pat + x + 1);
			}
			else
			{
				printf("%s\n", text + 1);
			}
		}
		else if(x > y)
		{
			printf("%s", text + 1);
			printf("%s\n", pat + x + 1);
		}
		else
		{
			printf("%s", pat + 1);
			printf("%s\n", text + y + 1);
		}
	}
}
这个模版好搓=。=
#include <iostream>
 #include <cstring>
 #include <cstdio>
 const int N=100001;
 using namespace std;
 int nextt[N];
 void next(char s[])
 {
     int i=1,j=0;
     int len=strlen(s);
     nextt[0]=-1;
     while(i<len)
     {
         if(j==-1||s[i]==s[j])
         {
             ++i;
             ++j;
             if(s[i]!=s[j])
                 nextt[i]=j;
             else
                 nextt[i]=nextt[j];
         }
         else
             j=nextt[j];
     }
 }
 int kmp(char ss[],char s[])
 {
     int len1=strlen(ss);
     int len2=strlen(s);
     next(s);
     int i=0,j=0;
     while(i<len1&&j<len2)
     {
         if(j==-1||ss[i]==s[j])
         {
             ++i;
             ++j;
         }
         else
             j=nextt[j];
     }
     if(i==len1)  
         return j; 
     return 0;
 }
 int main()
 {
     char str1[N],str2[N];
     while(~scanf("%s%s",str1,str2))
     {
         int x=kmp(str1,str2);
         int y=kmp(str2,str1);
         if(x==y)
         {
             if(strcmp(str1,str2)>0)
             {
                 printf("%s",str2);
                 printf("%s\n",str1+x);
             }
             else
             {
                 printf("%s",str1);
                 printf("%s\n",str2+x);
             }
         }
         else if(x>y)
         {
             printf("%s",str1);
             printf("%s\n",str2+x);
         }
         else
         {
             printf("%s",str2);
             printf("%s\n",str1+y);
         }
     }
     return 0;
}



© 著作权归作者所有

N3verL4nd
粉丝 1
博文 379
码字总数 481243
作品 0
朝阳
私信 提问
HDOJ 1009 FatMouse' Trade

FatMouse' TradeTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 81301 Accepted Submission(s): 28137 Problem Description FatM......

Dear_Jia
2017/09/30
0
0
反素数求解及相关题目

反素数 定义:对于任何正整数n,其约数个数记为f(n),例如f(6)=4;如果存在一个正整数n满足:对于任意的正整数x(0

my_sunshine26
2017/05/26
0
0
HDOJ 1811 Rank of Tetris

Rank of TetrisTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11206 Accepted Submission(s): 3206 Problem Description 自从L......

dear_jia
2018/04/18
0
0
HDOJ4548美素数

美素数Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 7741 Accepted Submission(s): 2714 Problem Description   小明对数的研......

zhagoodwell
2017/12/11
0
0
区间DP小结(附经典例题)

——这篇文章主要想总结下区间DP的经典题目,同时给自己复习巩固这方面知识点。 区间DP 一、定义 区间DP,顾名思义是在区间上DP,它的主要思想就是先在小区间进行DP得到最优解,然后再利用小...

my_sunshine26
2017/08/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周四乱弹 —— 当你简历注水但还是找到了工作

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @花间小酌 :#今日歌曲推荐# 分享成龙的单曲《男儿当自强》。 《男儿当自强》- 成龙 手机党少年们想听歌,请使劲儿戳(这里) @hxg2016 :刚在...

小小编辑
今天
2.9K
22
靠写代码赚钱的一些门路

作者 @mezod 译者 @josephchang10 如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。 今天给大家分享一个精彩的 GitHub 库,这个库整理...

高级农民工
昨天
5
0
用好项目管理工具,人人都可以成为项目经理

现在市面上的项目管理工具越来越多了,但是大多数都是一些协同工具或轻量项目管理工具。如果是多团队、跨部门使用或者企业级的项目管理,从管理思想到工具运用,需要适应企业的业务流程体系,...

cs平台
昨天
12
0
只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
69
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
32
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部