HDU 5343 MZL's Circle Zhou
MZL's Circle Zhou
This problem will be judged on HDU. Original ID: 5343
64-bit integer IO format: %I64d Java class name: Main
MZL's Circle Zhou is good at solving some counting problems. One day, he comes up with a counting problem:
You are given two strings a,b which consist of only lowercase English letters. You can subtract a substring x (maybe empty) from string a and a substring y (also maybe empty) from string b, and then connect them as x+y with x at the front and y at the back. In this way, a series of new strings can be obtained.
The question is how many different new strings can be obtained in this way.
Two strings are different, if and only if they have different lengths or there exists an integer i such that the two strings have different characters at position i.
Input
The first line of the input is a single integer T (T≤5), indicating the number of testcases.
For each test case, there are two lines, the first line is string a, and the second line is string b. 1<=|a|,|b|<=90000.
Output
Sample Input
2
acbcc
cccabc
bbbabbababbababbaaaabbbbabbaaaabaabbabbabbbaaabaab
abbaabbabbaaaabbbaababbabbabababaaaaabbaabbaabbaab
Sample Output
135
557539
Source
A、B两串分别建两个SAM处理,先将B串翻转,利用SAM(B)求以字符c结尾(开头)的子串个数。
对于SAM(A)中节点x,若x不能接受字符c,则将B串中以c开头的子串“接”在其后,构成Asub+Bsub的形式。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int maxn = ;
struct node{
int son[],f,len,alpha;
void init(){
memset(son,-,sizeof son);
f = -;
len = ;
}
};
struct SAM{
node e[maxn];
int tot,last;
int newnode(int len = ,int alpha = ){
e[tot].init();
e[tot].len = len;
e[tot].alpha = alpha;
return tot++;
}
void init(){
tot = last = ;
newnode();
}
void add(int c){
int p = last,np = newnode(e[p].len + ,c);
while(p != - && e[p].son[c] == -){
e[p].son[c] = np;
p = e[p].f;
}
if(p == -) e[np].f = ;
else{
int q = e[p].son[c];
if(e[p].len + == e[q].len) e[np].f = q;
else{
int nq = newnode();
e[nq] = e[q];
e[nq].len = e[p].len + ;
e[np].f = e[q].f = nq;
while(p != - && e[p].son[c] == q){
e[p].son[c] = nq;
p = e[p].f;
}
}
}
last = np;
}
}sam;
char a[maxn],b[maxn];
ULL dp[];
int main(){
int kase;
scanf("%d",&kase);
while(kase--){
scanf("%s%s",a,b);
reverse(b,b + strlen(b));
sam.init();
node *e = sam.e;
memset(dp,,sizeof dp);
for(int i = ; b[i]; ++i)
sam.add(b[i] - 'a');
for(int i = ; i < sam.tot; ++i)
dp[e[i].alpha] += e[i].len - e[e[i].f].len;
sam.init();
ULL ret = ;
for(int i = ; a[i]; ++i)
sam.add(a[i] - 'a');
for(int i = ; i < sam.tot; ++i){
ret += e[i].len - e[e[i].f].len;
for(int j = ; j < ; ++j)
if(e[i].son[j] == -) ret += dp[j]*(e[i].len - e[e[i].f].len);
}
printf("%I64u\n",ret + );
}
return ;
}
最新文章
- STM32f10xxx 之 GPIO口配置
- LDAP与禅道
- linux 安装vbox增强工具
- Visual Studio 2008打开vs2010解决方案的方法
- 【java】serialVersionUID作用
- 手势识别(一)--手势基本概念和ChaLearn Gesture Challenge
- getHibernateTemplate() 一直报NullPointerException 错误
- MySQL 时间戳(Timestamp)函数
- Eclipse vim插件安装使用
- BZOJ 2789: [Poi2012]Letters( BIT )
- WSDL中文版——详解
- Android模拟器调试html5 app
- java 注意事项---避免踩坑
- 【转】SQL数据库日志文件收缩
- Python字符串的格式化,看这一篇就够了
- xCode 升级9.3之后巨卡
- java中garadle工程没有src问题
- 启用mapredure历史服务器方法
- JS多重判断 / ES6 includes
- js中的call,apply,bind区别
热门文章
- go语言笔记——map map 默认是无序的,不管是按照 key 还是按照 value 默认都不排序
- codeforces 949B A Leapfrog in the Array
- linux安装 pip和setuptools
- 创建 /dev/video0 节点 (转载)
- P2924 [USACO08DEC]大栅栏Largest Fence
- @RequestParam 和 @RequestBody 接受的时间格式
- POI上传Excel的小问题处理
- [转]我是蒟蒻,但我有我的OI信仰
- 涨知识III - 百度2016校园招聘——移动软件研发工程师
- 大话设计模式--DI(依赖注入)