从键盘输入主串s以及子串t1和t2。编写程序，将主串s中所有t1子串替换为t2子串，输出替换后得到的串以及t1被替换的次数。要求子串查找采用改进KMP算法。

在Python中，你可以通过实现KMP算法（Knuth-Morris-Pratt 算法）来解决这个问题。首先，你需要创建两个函数：一个是构建next数组用于KMP匹配，另一个是实际的替换功能。下面是大致的步骤：

1. **构建next数组**:
KMP算法的核心是计算子串前缀最长公共部分的长度，这会帮助我们在遇到不匹配字符时跳过多余的搜索。你可以通过遍历t1创建next数组。

def get_next(t1):
    next_array = [0] * len(t1)
    j = -1
    for i in range(1, len(t1)):
        while j >= 0 and t1[i] != t1[j + 1]:
            j = next_array[j]
        if t1[i] == t1[j + 1]:
            j += 1
        next_array[i] = j
    return next_array

2. **查找并替换子串**:
使用`get_next`函数，我们可以遍历主串`s`，每次找到`t1`的开始位置就进行替换，并更新计数。

def replace_substrings(s, t1, t2):
    count = 0
    next_t1 = get_next(t1)
    result = ''
    index = 0
    for char in s:
        if index < len(t1) and char == t1[index]:
            index += 1
        else:
            if index > 0:
                index = next_t1[index - 1]
            if index == len(t1):  # 找到了一个完整的t1
                result += t2
                index = 0
                count += 1
            else:
                result += char
    return result, count

**示例使用：**

s = input("请输入主串s：")
t1 = input("请输入子串t1：")
t2 = input("请输入替换后的子串t2：")
result, replacements = replace_substrings(s, t1, t2)
print(f"替换后字符串：{result}")
print(f"{t1}被替换的次数：{replacements}次")