一、题意重述（最清晰版本）

给定：

• 字符串 $s$，长度 $n$
• 字符串 $t$，长度 $m$（$n\le m$）

对每个分割位置 $i$（$1\le i < n$），把 $s$ 切成两段：

$$x = s[1..i],\quad y = s[i+1..n]$$

问：能否把 $t$ 分割成若干段，每一段都是 $x$ 或 $y$？ 如果可以，输出 $\boldsymbol 1$，否则 $\boldsymbol 0$。 最终输出一个长度为 $n-1$ 的二进制串。

---

二、问题形式化

对一对字符串 $(x,y)$，称其是**合法（优美）**的，当且仅当：

$$t = a_1 + a_2 + \dots + a_k$$

其中每个 $a_j \in \{x,y\}$。

我们需要对 $s$ 的每一个前缀后缀切割判断合法性。

---

三、核心观察（解题关键）

1. $x,y$ 长度固定 设 $|x|=l_1,\ |y|=l_2$。 那么 $t$ 的任何分割方式，总长度必须满足：

   $$a\cdot l_1 + b\cdot l_2 = m$$

   其中 $a,b$ 是非负整数。

2. 字符串必须完全匹配 不仅长度要满足，每一段的字符内容也必须完全等于 $x$ 或 $y$。

3. 贪心匹配足够判定 从左到右扫描 $t$：

   • 能匹配 $x$ 就匹配 $x$
   • 能匹配 $y$ 就匹配 $y$ 只要有一种方式走完整个串，就是合法。

---

四、标程核心技术

1. 字符串哈希（Hash）

标程使用自定义模数哈希：

$$H[i] = H[i-1] \times base + val(s[i])$$

用于 $O(1)$ 比较任意子串是否相等。

2. 快速子串比较

inline Hash SUM(const int l, const int r, const Hash *s) {
    return s[r] - s[l - 1] * pw[r - l + 1];
}

作用：$O(1)$ 获取子串 $s[l..r]$ 的哈希值。

3. 最小循环节检测

标程预处理了 $s$ 的最小循环节：

for (int i = 1; i <= n; i++) {
    if (n % i == 0 && check(1, n, S[i], i, S)) {
        st = S[i];
        mnlen = i;
        break;
    }
}

作用：快速处理 $x,y$ 成倍数关系的情况，大幅加速。

---

五、标程主逻辑详解

1. 输入与哈希预处理

cin >> n >> m >> s >> t;
s = ' ' + s; // 改为 1 下标
t = ' ' + t;

// 计算 s 的前缀哈希
for (int i = 1; i <= n; i++)
    S[i] = S[i-1] * base + Hash(s[i]-'a'+1);

// 计算 t 的前缀哈希
for (int i = 1; i <= m; i++)
    T[i] = T[i-1] * base + Hash(t[i]-'a'+1);

---

2. 对每个分割点 i 进行判断

for (int i = 1; i < n; i++)
    putchar('0' ^ (i <= n - i ? 
        calc(1, i, i+1, n, i, n-i) : 
        calc(i+1, n, 1, i, n-i, i)
    ));

• 较短的串放前面，减少计算量
• 调用 calc 判断是否能分割 $t$

---

3. calc 函数（核心判断）

inline bool calc(
    int L1,int R1, int L2,int R2, 
    int l1,int l2
) {
    Hash s1 = SUM(L1,R1, S); // x 的哈希
    Hash s2 = SUM(L2,R2, S); // y 的哈希

    // 贪心匹配 t：尽可能用 s1，匹配不到就用 s2
    int ed = 0;
    while (ed <= m) {
        // 最多能连续匹配多少个 s1
        int cnt = 最大连续 s1 匹配数;
        
        // 尝试匹配 s2
        bool found = 尝试在附近匹配 s2;
        
        if (!found) return 0;
    }
    return 1;
}

逻辑：

1. 从左到右扫描 $t$
2. 尽可能多吃 $x$
3. 吃不动时，尝试匹配一个 $y$
4. 重复直到结束
5. 能走完就是合法

---

六、标程优化点（为什么能过 1e7 数据）

1. 1 下标字符串：避免边界错误
2. 短串优先：减少二分次数
3. 最小循环节特判：倍数串直接数学判定
4. 二分最长匹配：$O(\log m)$ 求连续匹配数
5. 快速哈希：$O(1)$ 子串比较
6. 仅回溯 2 步：保证线性复杂度

总复杂度：

$$O(\sum m)$$

完美应对 $m \le 5\times 10^6,\ \sum m \le 10^7$。

---

七、样例解释（第一组样例）

输入：

3 5
aba
ababa

• 分割 $i=1$：$x=\texttt{a},\ y=\texttt{ba}$ $\texttt{ababa} = \texttt{a+ba+ba}$ ✔️

• 分割 $i=2$：$x=\texttt{ab},\ y=\texttt{a}$ $\texttt{ababa} = \texttt{ab+ab+a}$ ✔️

输出：

11

---

八、标程代码整体结构总结

模块	作用
mod_int	安全模数哈希，防冲突
SUM	$O(1)$ 子串哈希
check	判断子串是否由某个串重复构成
calc	贪心判断 $t$ 是否能被 $x,y$ 分割
solve	预处理哈希，枚举每个分割点

---

九、最终结论（一句话）

本题是字符串哈希 + 贪心匹配的模板题：

1. 用哈希快速比较子串
2. 用贪心尽可能匹配长段
3. 对每个分割点输出结果

标程是最优解法，时间复杂度线性、常数极小、能轻松通过极限数据。

---