2017 Multi-University Training Contest - Team 4 Classic Quotation
Classic Quotation
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
online chatting, we can save what somebody said to form his ''Classic
Quotation''. Little Q does this, too. What's more? He even changes the
original words. Formally, we can assume what somebody said as a string S whose length is n. He will choose a continuous substring of S(or choose nothing), and remove it, then merge the remain parts into a complete one without changing order, marked as S′. For example, he might remove ''not'' from the string ''I am not SB.'', so that the new string S′ will be ''I am SB.'', which makes it funnier.
After doing lots of such things, Little Q finds out that string T occurs as a continuous substring of S′ very often.
Now given strings S and T, Little Q has k questions. Each question is, given L and R, Little Q will remove a substring so that the remain parts are S[1..i] and S[j..n], what is the expected times that T occurs as a continuous substring of S′ if he choose every possible pair of (i,j)(1≤i≤L,R≤j≤n) equiprobably? Your task is to find the answer E, and report E×L×(n−R+1) to him.
Note : When counting occurrences, T can overlap with each other.
In each test case, there are 3 integers n,m,k(1≤n≤50000,1≤m≤100,1≤k≤50000) in the first line, denoting the length of S, the length of T and the number of questions.
In the next line, there is a string S consists of n lower-case English letters.
Then in the next line, there is a string T consists of m lower-case English letters.
In the following k lines, there are 2 integers L,R(1≤L<R≤n) in each line, denoting a question.
8 5 4
iamnotsb
iamsb
4 7
3 7
3 8
2 7
1
0
0
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <bitset>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <cassert>
#include <ctime>
#define rep(i,m,n) for(i=m;i<=(int)n;i++)
#define mod 998244353
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define sys system("pause")
#define ls rt<<1
#define rs rt<<1|1
#define all(x) x.begin(),x.end()
const int maxn=5e4+;
const int N=5e4+;
using namespace std;
ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}
ll qmul(ll p,ll q,ll mo){ll f=;while(q){if(q&)f=(f+p)%mo;p=(p+p)%mo;q>>=;}return f;}
ll qpow(ll p,ll q,ll mo){ll f=;while(q){if(q&)f=qmul(f,p,mo)%mo;p=qmul(p,p,mo)%mo;q>>=;}return f;}
int n,m,k,t,nxt[maxn],nxt1[][];
ll pref[maxn],preg[maxn],s[maxn][],suf[maxn][];
char a[maxn],b[maxn];
void init(char *a,char *b)
{
for(int i=;i<=n;i++)
{
pref[i]=preg[i]=;
for(int j=;j<=m;j++)
{
s[i][j]=suf[i][j]=;
}
}
nxt[]=-;
int j=-;
for(int i=;i<=m;i++)
{
while(!(j==-||b[j]==b[i]))j=nxt[j];
nxt[i+]=++j;
}
j=;
for(int i=;i<n;i++)
{
while(!(j==-||a[i]==b[j]))j=nxt[j];
if(i)preg[i]=preg[i-];
pref[i]=++j;
s[i][j]++;
if(j==m)preg[i]++;
}
for(int i=;i<n;i++)
{
preg[i]+=preg[i-];
for(int j=;j<=m;j++)
{
s[i][j]+=s[i-][j];
}
}
for(int i=;i<=m;i++)
{
for(int j='a';j<='z';j++)
{
int k=i;
while(!(k==-||j==b[k]))k=nxt[k];
nxt1[i][j-'a']=k+;
}
}
for(int i=n-;i>=;i--)
{
for(int j=;j<=m;j++)
{
int tmp=nxt1[j][a[i]-'a'];
suf[i][j]+=suf[i+][tmp];
if(tmp==m)suf[i][j]++;
}
}
for(int i=n-;i>=;i--)
{
for(int j=;j<=m;j++)
{
suf[i][j]+=suf[i+][j];
}
}
}
int main()
{
int i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
scanf("%s%s",a,b);
init(a,b);
while(k--)
{
int x,y;
scanf("%d%d",&x,&y);
ll ret=(n-y+)*preg[x-];
for(int i=;i<=m;i++)
{
ret+=s[x-][i]*suf[y-][i];
}
printf("%lld\n",ret);
}
}
return ;
}
最新文章
- java 内存回收(GC)的方式
- 关于eclipse在线下载安装android SDK没反应解决方法
- 翻译:Universal Image Loader
- [转]c#调用API截图
- centosx64位寄存器
- wcf系列5天速成——第一天 binding的使用(1)
- 图解 ENGLISH
- Windows下使用Sublime text3快速编辑Linux文件,写Shell
- 关于ArrayList的5道面试题
- application.properties 文件和 application.yml 文件的区别
- vuejs2.0如何获取dom元素自定义属性值
- 微信小程序调用快递物流查询API的实现方法
- PHP爬虫框架Snoopy的使用
- Python之__slots__ &;运算符重载反向运算
- cpu监控之三:mpstat命令
- MongoDB对Javascript的支持
- js倒计时发送验证码按钮
- 算法导论--装备线调度(升序&;amp;&;amp;降序输出)
- Python import random报错处理办法
- informix-時間格式的各種用法
热门文章
- 【POJ 2259】 Team Queue
- jeesite ckeditor数据库 HTML 被编码 的问题解决
- 湖南集训day6
- [App Store Connect帮助]二、 添加、编辑和删除用户(4)更改用户的 App 访问权限
- Vue电商SKU组合算法问题
- CF 436D 最小生成树
- Java系列学习(十三)-字符串
- no斜体 背景图片坐标
- JS——“==”与“===”
- SQL基本操作——DROP撤销索引、表以及数据库