HDU6135 拓展KMP模板
2024-10-08 01:32:14
emmm...模板,虽然每太搞懂
#include <iostream>
#include <cstdio>
#include <string.h>
#pragma warning ( disable : 4996 )
using namespace std; inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
const int inf = 0x3f3f3f3f;
const int maxn = 1e6+; char str[maxn], nstr[maxn];
int nex[maxn], extend[maxn];
int len, nlen;
long long ans, mod = ; void init()
{
ans = ;
memset( str, , sizeof(str) );
memset( nstr, , sizeof(nstr) ); scanf( "%s", str ); len = strlen(str); reverse(str, str+len);
scanf( "%s", nstr ); nlen = strlen(nstr); reverse(nstr, nstr+nlen);
} void getNext()
{
nex[] = nlen;
int po, far; //po表示目前匹配的起始点,far表示最远点 for (int i = , j = -; i < nlen; i++, j-- )
{
if ( j < || i + nex[i-po] >= far )
{
if(j<) { far=i;j++; }
while(far<nlen&&nstr[far]==nstr[j])
{ far++; j++; } nex[i] = j;
po = i;
}
else
nex[i] = nex[i-po];
}
} void getExtend()
{
int po, far; for ( int i = , j = -; i < len; i++, j-- )
{
if ( j < || i + nex[i-po] >= far )
{
if(j<) { far=i;j++; }
while(far<len && j<nlen && str[far]==nstr[j] )
{ far++; j++; } extend[i] = j;
po = i;
}
else
extend[i] = nex[i-po];
}
} int main()
{
int all; cin >> all;
while (all--)
{
init();
getNext();
getExtend(); long long tmp;
for ( int i = ; i < len; i++ )
{
tmp = (long long)extend[i];
ans = ( ans + tmp*(tmp+)/ ) % mod;
}
printf( "%lld\n", ans );
}
return ;
}
最新文章
- Spark学习(四) -- Spark作业提交
- iOS 开发之控件快速学习(一)
- svn使用--all-static编译,移植到其它系统上可能使setlocale等GLIBC相关库函数调用失败
- springMVC源码分析之拦截器
- 【转载】使用LFM(Latent factor model)隐语义模型进行Top-N推荐
- Codeforces 519E A and B and Lecture Rooms [倍增法LCA]
- 通过外网IP访问内网
- Codeforces Round #340 (Div. 2) E. XOR and Favorite Number 莫队算法
- 使用 xcode 8 构建版本 iTunes Connect 获取不到应用程序的状态
- uploadify 上传
- Selector中的各种状态详解
- list类型for遍历
- poj1159 dp(滚动数组优化)
- 在SAE上搭建自定义版本WordPress, 并用SAE Storage代替WordPress Uploads
- ImageMagick 压缩图片 方法
- php框架中的phalcon框架的安装,及初步认识,从表单提交简单的数据到数据库中
- cocos2d-js:游戏进入后台和返回游戏的事件捕获和处理
- asp.net mvc如何获取url的相关信息
- Centos 装系统 配置网卡,校准时间
- 微信小程序获取当前位置
热门文章
- P1305 新二叉树 /// 二叉树的先序遍历
- POJ - 3294~Relevant Phrases of Annihilation SPOJ - PHRASES~Substrings POJ - 1226~POJ - 3450 ~ POJ - 3080 (后缀数组求解多个串的公共字串问题)
- 如何将制定目录加入到PYTHONPATH
- pywebview gui=&#39;cef&#39; 生成app报错—— 中断点 已到达中断点
- Java驼峰和下划线互相转化
- 莫烦pytorch学习笔记(二)——variable
- ArcMap10.2 中制作符号库
- 使用Native API 创建进程
- 表单单选按钮input[type=";radio";]
- 04_springmvc注解开发