Simpsons’ Hidden Talents HDU - 2594(拓展kmp)
2024-08-27 02:23:41
Sample Input
clinton
homer
riemann
marjorie
Sample Output
0
rie 3 看输出才题意。。。
拓展kmp特征很明显嘛。。。。
注意开始就匹配到尾的情况
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff;
int nex[maxn], ex[maxn]; void get_next(char *s)
{
int i=, j, po, len = strlen(s);
nex[] = len;
while(i+ < len && s[i] == s[i+])
i++;
nex[] = i;
po = ;
for(int i=; i<len; i++)
{
if(i+nex[i-po] < po + nex[po])
nex[i] = nex[i-po];
else
{
j = po + nex[po] - i;
if(j < ) j = ;
while(i + j < len && s[i+j] == s[j])
j++;
nex[i] = j;
po = i;
}
}
} int get_ex(char *s1, char *s2)
{
int i=, j, po, len1 = strlen(s1), len2 = strlen(s2);
get_next(s2);
while(s1[i] == s2[i] && i < len1 && i < len2)
i++;
ex[] = i;
if(i == len1)
return ;
po = ;
for(int i=; i<len1; i++)
{
if(i + nex[i - po] < po + ex[po])
ex[i] = nex[i-po];
else
{
j = po + ex[po] - i;
if(j < ) j = ;
while(i + j < len1 && j < len2 && s1[i+j] == s2[j])
j++;
ex[i] = j;
po = i;
if(ex[i] == len1 - i)
return i + ;
}
}
return ;
} char s1[maxn], s2[maxn];
int main()
{
while(~rs(s1))
{
rs(s2);
int flag = get_ex(s2, s1);
int len = strlen(s2);
if(flag)
{
rep(i, flag-, len)
cout<<s2[i];
cout<<" ";
cout<< ex[flag-] <<endl;
}
else
cout<< "" <<endl; } return ;
}
最新文章
- Log4net入门(日志文件篇)
- odoo种种
- SharePoint 2013 版本功能对比
- JS常用工具函数
- jQuery 更改checkbox的状态,无效
- Bootstrap 类解析
- 【POJ 1035】Spell checker
- android之TabHost(上)
- BZOJ3888 [Usaco2015 Jan]Stampede
- 纯手写分页控件CSS+JS+SQL
- java文件过滤器
- 巧妙使用checkbox制作纯css动态导航栏
- 详细讲解Hadoop源码阅读工程(以hadoop-2.6.0-src.tar.gz和hadoop-2.6.0-cdh5.4.5-src.tar.gz为代表)
- iOS开发常识
- 【转】论文、会议、期刊评价|Indicate paper, conference, Journal
- Python之FTP多线程下载文件之分块多线程文件合并
- centos7 安装openvswitch
- XP和win7的软件崩溃提示
- 『练手』手写一个独立Json算法 JsonHelper
- Eclipse中三种设置编码格式的方法
热门文章
- gitlab在push代码的时候报错
- Yii2 使用 bootboxJS美化confirm窗口
- The specified value ";2019-1-2"; does not conform to the required format, ";yyyy-MM-dd";
- selenium自动化之稳定版本环境介绍
- 抓包工具Charles学习总结
- Python解包参数列表及 Lambda 表达式
- vim—多行注释、取消多行注释
- H2O Driverless AI
- Scrum立会报告+燃尽图(十月十三日总第四次):前期宣传相关工作
- Xftp安装和使用的视频录制方法