A16441 | Pumping Lemma
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
[Tanchiky & Siromaru - Crystal Gravity](https://soundcloud.com/messi-ola/crystal-gravity-tanchiky-vs)
⠀
You are given two strings $s$ , $t$ of length $n$ , $m$ , respectively. Both strings consist of lowercase letters of the English alphabet.
Count the triples $(x, y, z)$ of strings such that the following conditions are true:
- $s = x+y+z$ (the symbol $+$ represents the concatenation);
- $t = x+\underbrace{ y+\dots+y }_{k \text{ times}} + z$ for some integer $k$ .
⠀
You are given two strings $s$ , $t$ of length $n$ , $m$ , respectively. Both strings consist of lowercase letters of the English alphabet.
Count the triples $(x, y, z)$ of strings such that the following conditions are true:
- $s = x+y+z$ (the symbol $+$ represents the concatenation);
- $t = x+\underbrace{ y+\dots+y }_{k \text{ times}} + z$ for some integer $k$ .
输入格式
The first line contains two integers $n$ and $m$ ( $1 \leq n < m \leq 10^7$ ) — the length of the strings $s$ and $t$ , respectively.
The second line contains the string $s$ of length $n$ , consisting of lowercase letters of the English alphabet.
The third line contains the string $t$ of length $m$ , consisting of lowercase letters of the English alphabet.
The second line contains the string $s$ of length $n$ , consisting of lowercase letters of the English alphabet.
The third line contains the string $t$ of length $m$ , consisting of lowercase letters of the English alphabet.
输出格式
Output a single integer: the number of valid triples $(x, y, z)$ .
输入输出样例
输入 #1
4 8 abcd abcbcbcd
输出 #1
1
输入 #2
3 5 aaa aaaaa
输出 #2
5
输入 #3
12 16 abbababacaab abbababababacaab
输出 #3
8
In the first test case, the only valid triple is $(x, y, z) = (\texttt{"a"}, \texttt{"bc"}, \texttt{"d"})$ . In fact,
- $\texttt{"abcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"d"}$ ;
- $\texttt{"abcbcbcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"d"}$ .
In the second test case, there are $5$ valid triples:
- $(x, y, z) = (\texttt{""}, \texttt{"a"}, \texttt{"aa"})$ ;
- $(x, y, z) = (\texttt{""}, \texttt{"aa"}, \texttt{"a"})$ ;
- $(x, y, z) = (\texttt{"a"}, \texttt{"a"}, \texttt{"a"})$ ;
- $(x, y, z) = (\texttt{"a"}, \texttt{"aa"}, \texttt{""})$ ;
- $(x, y, z) = (\texttt{"aa"}, \texttt{"a"}, \texttt{""})$ .
In the third test case, there are $8$ valid triples:
- $(x, y, z) = (\texttt{"ab"}, \texttt{"ba"}, \texttt{"babacaab"})$ ;
- $(x, y, z) = (\texttt{"abb"}, \texttt{"ab"}, \texttt{"abacaab"})$ ;
- $(x, y, z) = (\texttt{"abba"}, \texttt{"ba"}, \texttt{"bacaab"})$ ;
- $(x, y, z) = (\texttt{"ab"}, \texttt{"baba"}, \texttt{"bacaab"})$ ;
- $(x, y, z) = (\texttt{"abbab"}, \texttt{"ab"}, \texttt{"acaab"})$ ;
- $(x, y, z) = (\texttt{"abb"}, \texttt{"abab"}, \texttt{"acaab"})$ ;
- $(x, y, z) = (\texttt{"abbaba"}, \texttt{"ba"}, \texttt{"caab"})$ ;
- $(x, y, z) = (\texttt{"abba"}, \texttt{"baba"}, \texttt{"caab"})$ .
- $\texttt{"abcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"d"}$ ;
- $\texttt{"abcbcbcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"d"}$ .
In the second test case, there are $5$ valid triples:
- $(x, y, z) = (\texttt{""}, \texttt{"a"}, \texttt{"aa"})$ ;
- $(x, y, z) = (\texttt{""}, \texttt{"aa"}, \texttt{"a"})$ ;
- $(x, y, z) = (\texttt{"a"}, \texttt{"a"}, \texttt{"a"})$ ;
- $(x, y, z) = (\texttt{"a"}, \texttt{"aa"}, \texttt{""})$ ;
- $(x, y, z) = (\texttt{"aa"}, \texttt{"a"}, \texttt{""})$ .
In the third test case, there are $8$ valid triples:
- $(x, y, z) = (\texttt{"ab"}, \texttt{"ba"}, \texttt{"babacaab"})$ ;
- $(x, y, z) = (\texttt{"abb"}, \texttt{"ab"}, \texttt{"abacaab"})$ ;
- $(x, y, z) = (\texttt{"abba"}, \texttt{"ba"}, \texttt{"bacaab"})$ ;
- $(x, y, z) = (\texttt{"ab"}, \texttt{"baba"}, \texttt{"bacaab"})$ ;
- $(x, y, z) = (\texttt{"abbab"}, \texttt{"ab"}, \texttt{"acaab"})$ ;
- $(x, y, z) = (\texttt{"abb"}, \texttt{"abab"}, \texttt{"acaab"})$ ;
- $(x, y, z) = (\texttt{"abbaba"}, \texttt{"ba"}, \texttt{"caab"})$ ;
- $(x, y, z) = (\texttt{"abba"}, \texttt{"baba"}, \texttt{"caab"})$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted