HDU 2594(求最长公共前后缀 kmp)

Stella981
• 阅读 565

题意是在所给的两个字符串中找最长的公共前后缀,即第一个字符串前缀和第二个字符串后缀的最长相等串。

思路是将两个字符串拼接在一起,然后直接套用 kmp 算法即可。

要注意用 next 会报编译错误,改成 Next 才过……但 next 确实不是 c++ 关键字。

代码如下:

HDU 2594(求最长公共前后缀 kmp) HDU 2594(求最长公共前后缀 kmp)

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 const int N=50000+5;
 6 char a[N*2],b[N];
 7 int Next[N*2];
 8 void getNext()
 9 {
10     Next[0] = -1;
11     int i=1,j=0,len=strlen(a);
12     while(i<len)
13     {
14         if(j==-1||a[i]==a[j])
15         {
16             i++;j++;
17             Next[i]=j;
18         }
19         else
20             j=Next[j];
21     }
22 }
23 int main()
24 {
25     while(~scanf("%s%s",a,b))
26     {
27         int lena=strlen(a),lenb=strlen(b);
28         strcat(a,b);//将b字符串连在a字符串后
29         getNext();//求解Next数组
30         int ans=Next[strlen(a)];
31         while(ans>lenb||ans>lena) ans=Next[ans];
32         if(ans==0) puts("0");
33         else
34         {
35             a[ans] = 0;
36             printf("%s %d\n",a,ans);
37         }
38     }
39     return 0;
40 }

View Code

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Karen110 Karen110
2年前
一篇文章带你了解JavaScript日期
日期对象允许您使用日期(年、月、日、小时、分钟、秒和毫秒)。一、JavaScript的日期格式一个JavaScript日期可以写为一个字符串:ThuFeb02201909:59:51GMT0800(中国标准时间)或者是一个数字:1486000791164写数字的日期,指定的毫秒数自1970年1月1日00:00:00到现在。1\.显示日期使用
Wesley13 Wesley13
2年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Stella981 Stella981
2年前
JS 苹果手机日期显示NaN问题
问题描述newDate("2019122910:30:00")在IOS下显示为NaN原因分析带的日期IOS下存在兼容问题解决方法字符串替换letdateStr"2019122910:30:00";datedateStr.repl
Stella981 Stella981
2年前
JavaScript常用函数
1\.字符串长度截取functioncutstr(str,len){vartemp,icount0,patrn/^\x00\xff/,strre"";for(vari
Wesley13 Wesley13
2年前
AGC 041D
考虑限制一定是对于前缀和后缀的,并且显然相交的前后缀可以不考虑。然后还可以发现只用考虑最长的那一段的条件,即$\\lfloor\\frac{n1}{2}\\rfloor$和$\\lfloor\\frac{n1}{2}\\rfloor1$的长度。可以将原序列分成两个部分。如下:$${AA|(C)|B}$$我们把
Wesley13 Wesley13
2年前
unity将 -u4E00 这种 编码 转汉字 方法
 unity中直接使用 JsonMapper.ToJson(对象),取到的字符串,里面汉字可能是\\u4E00类似这种其实也不用转,服务器会通过类似fastjson发序列化的方式,将json转对象,获取对象的值就是中文但是有时服务器要求将传参中字符串中类似\\u4E00这种转汉字,就需要下面 publ
Stella981 Stella981
2年前
LeetCode:(14. 最长公共前缀!!!!!)
题目:14\.最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串“”。示例1:输入:\“flower”,“flow”,“flight”\输出:“fl”示例2:输入:\“dog”,“racecar”,“car”\输出:“”
Python进阶者 Python进阶者
4个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这