思路

• 唯一分割的结构：由于 $x$ 不含 $d$ 与 $p$，整串必然呈现反复的模式：一段由非 $d,p$ 字符构成的连续块 $x$，随后紧跟着 "dp"；如此反复直到串末。

• 线性扫描：从左到右扫描：

  • 累积一段由非 $d,p$ 字符组成的连续块作为当前的 $x$；
  • 读到 "dp" 后结束该段，将该 $x$ 放入集合；
  • 跳过 "dp" 继续下一段。

• 正确性：每一段的 $x$ 恰为紧邻其后的 "dp" 之前的最长非 $d,p$ 连续块；由于 $x$ 不能含 $d,p$ 且分割唯一，上述扫描会精确得到每个 $x$，且不会遗漏或重复切分。

• 复杂度：时间 $O(n)$，空间 $O(k)$，其中 $n$ 为 $\text{length}(s)$，$k$ 为不同 $x$ 的数量。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s;
	if (!(cin >> s)) return 0;

	size_t n = s.size();
	size_t i = 0;
	// 使用 string_view 存储对原串的“视图”，避免大量子串拷贝
	unordered_set<string_view> kinds;
	kinds.reserve(1 << 15);

	while (i < n) {
		size_t j = i;
		// 累积当前段的 x：由非 d/p 的字符构成
		while (j < n && s[j] != 'd' && s[j] != 'p') ++j;

		// 将 x 视图插入集合
		string_view x(s.data() + i, j - i);
		kinds.insert(x);

		// 跳过紧随其后的 "dp"
		// 题意保证输入合法，这里不做越界与合法性检查
		i = j + 2;
	}

	cout << kinds.size() << '\n';
	return 0;
}

Python

import sys

s = sys.stdin.readline().strip()
n = len(s)
i = 0
kinds = set()

while i < n:
	# 累积当前段的 x：由非 d/p 的字符构成
	j = i
	while j < n and s[j] not in ('d', 'p'):
		j += 1

	# 记录 x
	kinds.add(s[i:j])

	# 跳过紧随其后的 "dp"（题意保证合法）
	i = j + 2

print(len(kinds))

Java

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine().trim();
		int n = s.length();
		int i = 0;
		HashSet<String> kinds = new HashSet<>();

		while (i < n) {
			// 累积当前段的 x：由非 d/p 的字符构成
			int j = i;
			while (j < n && s.charAt(j) != 'd' && s.charAt(j) != 'p') {
				j++;
			}

			// 记录 x
			kinds.add(s.substring(i, j));

			// 跳过紧随其后的 "dp"（题意保证合法）
			i = j + 2;
		}

		System.out.println(kinds.size());
	}
}

题目内容

已知一套试卷包含多个 $x-dp$ 算法，即 $x$ 类型的 $dp$ (保证 $x$ 不为空且不含 $'d’$ 和 $'p’$ 两个字符)。例如 $sosdp$， $adp$ ，其拼接起来为 $sosdpadp$，构成了一套完整的试卷。

现在便可以得到该试卷中存在若干类型的 $dp$ 算法，你需要知道有多少种本质不同的 $dp$ 算法，即有多少种不同 $x$ 类型的算法。

保证 $s$ 可以被唯一地分割为一个或多个形如 $x+dp$ 的段。

输入描述

在一行上输入一个仅由小写字母组成的字符串 $s(3≤length(s)≤ 10^6)$ ，表示试卷。

输出描述

输出一个整数，表示给定试卷中存在多少种不同类型的 $dp$ 算法。

样例1

输入

sosdpadp

输出

2

样例2

输入

adpbdpadp

输出

2