P1369. 编码分割问题

题目描述

考虑一种著名压缩算法中使用的编码方案。假设我们只编码小写字母序列。每个字符序列可以被编码为一个由$(p_i, r_i)$对组成的序列，其中：

• 当$p_i = 0$时，$r_i$是一个字符
• 当$p_i > 0$时，$r_i$是一个满足$0 < r_i \leq p_i$的整数

解码过程如下：

1. 对于$(0, r_i)$：直接将字符$r_i$添加到已解码序列末尾
2. 对于$(p_i, r_i)$（$p_i > 0$）：从当前序列末尾向前数$p_i$个位置开始，复制$r_i$个字符添加到序列末尾

例如，编码序列$(0,a),(1,1),(0,b),(3,3),(3,3),(3,2),(0,c)$的解码过程：

1. $(0,a)$ → "a"
2. $(1,1)$ → "aa"（复制最后1个字符1次）
3. $(0,b)$ → "aab"
4. $(3,3)$ → "aabaab"（从倒数第3位开始复制3个字符）
5. $(3,3)$ → "aabaabaab"
6. $(3,2)$ → "aabaabaabaa"（复制倒数第3位开始的2个字符）
7. $(0,c)$ → "aabaabaabaac"

给定编码序列$C_w$，问题要求计算有多少种方式可以将其分割为$C_uC_v$，使得：

1. 解码后的$w=uv$（$u$和$v$都不为空）
2. $C_u$和$C_v$都是有效的编码序列

输入格式

• 由多个块组成，每个块描述一个编码序列$C_w$
• 每行包含：
  • 两个整数$p_i\ r_i$（$r_i \leq p_i < 1000$），或
  • "0"后跟一个字符
• 每个块以空行结束

输出格式

• 对于每个输入块，输出满足条件的分割方式数量

样例输入

0 a
1 1
0 b
3 3
3 3
3 2
0 c

样例输出

1

题目来源

Central Europe 1997