注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1867  

2013-02-08 21:14:48|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1867
题意:
求最长相同的串a后缀和串b的前缀(或者是最长相同的串b后缀和串a的前缀),进行合并,得到长度最短的a+b,且字典序最小
解题思路:
KMP的运用,利用KMP求出
最长相同的串a后缀和串b的前缀 和 最长相同的串b后缀和串a的前缀,然后按较长的进行输出

/*
* test2.cpp
*
* Created on: 2013-2-8
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define N 100010
char s1[N],s2[N];//s1为主串,s2为模式串
int next1[N],next2[N];

void getnext(int next[],char s[])
{
int len,i=0,j=-1;
next[0]=-1;
len=(int)strlen(s);
while(i<len)
{
if(j==-1 || s[i]==s[j])
{
i++;j++;
if(s[i] != s[j])//优化
next[i]=j;
else
next[i]=next[j];
}
else
j=next[j];
}
}

int KMP(char s1[],char s2[],int next[])
{
//返回最长相同的主串后缀和模式串前缀
int i,j,len1,len2;
i=0;j=0;
len1=(int)strlen(s1);
len2=(int)strlen(s2);
while(i<len1)
{
if(j<0 || s1[i]==s2[j])
{
i++;j++;
}
else
j=next[j];
}
return j;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int len1,len2;
while(scanf("%s %s",s1,s2)!=EOF)
{
getnext(next1,s2);
len1=KMP(s1,s2,next1);

getnext(next2,s1);
len2=KMP(s2,s1,next2);

if(len1==len2)
{
if(strcmp(s1,s2)<0)
printf("%s%s\n",s1,s2+len1);
else
printf("%s%s\n",s2,s1+len1);
}
else if(len1 > len2)
printf("%s%s\n",s1,s2+len1);
else
printf("%s%s\n",s2,s1+len2);
}
return 0;
}


  评论这张
 
阅读(137)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018