xtu字符串 C. Marlon's String
2024-08-29 14:05:38
C. Marlon's String
Time Limit: 2000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: Main
Long long ago, there was a coder named Marlon. One day he picked two string on the street. A problem suddenly crash his brain...
Let Si..j denote the i-th character to the j-th character of string S.
Given two strings S and T. Return the amount of tetrad (a,b,c,d) which satisfy Sa..b + Sc..d = T , a≤b and c≤d.
The operator + means concate the two strings into one.
Input
The first line of the data is an integer Tc. Following Tc test cases, each contains two line. The first line is S. The second line is T. The length of S and T are both in range [1,100000]. There are only letters in string S and T.
Output
For each test cases, output a line for the result.
Sample Input
1
aaabbb
ab
Sample Output
9 解题:与扩展KMP无关,与前缀有关。。。直接KMP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int fail[];
char pa[],s[];
int a[],b[];
void kmp(int *arr){
int i,j,k;
fail[] = fail[] = ;
for(i = ; pa[i]; i++){
j = fail[i];
while(j && pa[i] != pa[j]) j = fail[j];
fail[i+] = pa[j] == pa[i] ? j+:;
}
for(j = i = ; s[i]; i++){
while(j && s[i] != pa[j]) j = fail[j];
if(pa[j] == s[i]){
arr[++j]++;
}
}
for(i = strlen(pa); i >= ; i--)
if(fail[i]) arr[fail[i]] += arr[i];
}
int main(){
int t,i,len;
LL ans;
scanf("%d",&t);
while(t--){
scanf("%s %s",s,pa);
memset(a,,sizeof(a));
memset(b,,sizeof(b));
kmp(a);
reverse(s,s+strlen(s));
reverse(pa,pa+strlen(pa));
kmp(b);
ans = ;
for(len = strlen(pa),i = ; i < len; i++)
ans += (LL)a[i]*b[len-i];
printf("%lld\n",ans);
}
return ;
}
最新文章
- linux 压缩 解压zip 命令
- mac安装Aws cli失败
- JS 的线程、事件循环、任务队列简介
- 为DELL inspiron 14R安装CentOS X64 6.4
- leptonica 学习笔记2——pixBackgroundNormSimple
- C语言中头文件<;stdio.h>;中的#ifndef _STDIO_H_
- JavasScript实现调查问卷插件
- Win10下Mysql5.7.13,解压版安装流程
- strstr() strpos() 获取db报错,判断报错中是否包含字符串,判断错误类型
- UVA - 11427 Expect the Expected (概率dp)
- Java高级特性 第9节 Socket机制
- 【机器学习】K均值算法(I)
- Cookie深度解析
- chart.js应用中遇到的问题
- C++静态库与动态库(比较透彻)
- Kite(几何+镜面对称)
- TFS 报错解决方案:tf400324
- codeblocks “can&#39;t find compiler executable in yourconfigured search ……”
- SED单行脚本快速参考(Unix 流编辑器)
- [海蜘蛛] 海蜘蛛 V8 全线无限试用版 免费发布破解教程