rule_解析`````````````````

"""编写一个Python函数，该函数接受两个参数：
一个文本文件【rule】和一个字符串【input】，
请根据文件中【rule】的替换规则返回一个字符串【output】。
def apply_replacement_rules(rules, input_string):
    # 你的代码【rule】

解析要求：
1、文本文件【rule】包含按顺序应用的替换规则。
2、每条规则是由空格分隔的两个字符串：s1 s2，其中s1和s2是不包含任何空格字符的字符串。
其含义是：对于输入字符串中的每个子字符串s1，
如果该子字符串没有被之前的任何规则更改过，
则将其替换为s2。

举例：
考虑文件rule.txt的内容如下（包含3条规则）：
abc cde
ab b
c a

它在输入字符串babcabdcdc上的工作过程如下：
1.第一条规则：b + cde + abdcdc #abc cde
2.第二条规则：b + cde + b + dcdc #ab b
3.第三条规则：b + cde + b + d + a + d + a #c a
（注意，尽管“cde”包含“c”，但它不会被第三条规则出发，因为它是第一条规则产生的新字符串，而不是来自原始字符串）
所以输出是 bcdebdada

请注意：参数规则【rule】不是固定的， 你的程序应该适用于任何顺序与任何替换规则，
如：c ab
abc cde
ab b
或
abcd ab
cde bcd
ade bc
请你尝试使用最优的时间复杂度来解决这个问题

解题思路：
一、先按行读取rule.txt文件，因其格式固定为每行一条规则，且每行格式为s1 s2，
读取时将其存为字典，该字典rule_dict格式为{n：[s1,s2]},n为行数
二、构造状态字典，用于存储字符串修改的历史状态及当前状态，该状态字典随规则顺序流动而更新。
如：输入字符串babcabdcdc：
1.第一条规则：b + cde + abdcdc #abc cde
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,3"]}}
字段说明：键1表示第一条规则，键1对应的值表示第一条规则运行后的状态，source_str表示
执行第一条规则之前的输入字符串，new_str表示执行第一条规则之后的输出字符串，change_index"表示
new_str中哪一段索引是被改变的索引
2.第二条规则：b + cde + b + dcdc #ab b
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,3"]},
2:{"source_str":"bcdeabdcdc","new_str":"bcdebdcdc","change_index":["1,3","4"]},
}
3.第三条规则：b + cde + b + d + a + d + a #c a
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,2,3"]},
2:{"source_str":"bcdeabdcdc","new_str":"bcdebdcdc","change_index":["1,2,3","4"]},
3:{"source_str":"bcdebdcdc","new_str":"bcdebdada","change_index":["1,2,3","4","6,8"]},
}
三、字符串按规则处理函数
传入rule_dict和原生字符串。按照规则进行处理：对于输入字符串中的每个子字符串s1，
如果该子字符串没有被之前的任何规则更改过（通过str_status判断有没有更改过），则将其替换为s2，
之后更新str_status"""
 

"""编写一个Python函数，该函数接受两个参数：
一个文本文件【rule】和一个字符串【input】，
请根据文件中【rule】的替换规则返回一个字符串【output】。
def apply_replacement_rules(rules, input_string):# 你的代码【rule】解析要求：
1、文本文件【rule】包含按顺序应用的替换规则。
2、每条规则是由空格分隔的两个字符串：s1 s2，其中s1和s2是不包含任何空格字符的字符串。
其含义是：对于输入字符串中的每个子字符串s1，
如果该子字符串没有被之前的任何规则更改过，
则将其替换为s2。举例：
考虑文件rule.txt的内容如下（包含3条规则）：
abc cde
ab b
c a它在输入字符串babcabdcdc上的工作过程如下：
1.第一条规则：b + cde + abdcdc #abc cde
2.第二条规则：b + cde + b + dcdc #ab b
3.第三条规则：b + cde + b + d + a + d + a #c a
（注意，尽管“cde”包含“c”，但它不会被第三条规则出发，因为它是第一条规则产生的新字符串，而不是来自原始字符串）
所以输出是 bcdebdada请注意：参数规则【rule】不是固定的， 你的程序应该适用于任何顺序与任何替换规则，
如：c ab
abc cde
ab b
或
abcd ab
cde bcd
ade bc
请你尝试使用最优的时间复杂度来解决这个问题解题思路：
一、先按行读取rule.txt文件，因其格式固定为每行一条规则，且每行格式为s1 s2，
读取时将其存为字典，该字典rule_dict格式为{n：[s1,s2]},n为行数
二、构造状态字典，用于存储字符串修改的历史状态及当前状态，该状态字典随规则顺序流动而更新。
如：输入字符串babcabdcdc：
1.第一条规则：b + cde + abdcdc #abc cde
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,3"]}}
字段说明：键1表示第一条规则，键1对应的值表示第一条规则运行后的状态，source_str表示
执行第一条规则之前的输入字符串，new_str表示执行第一条规则之后的输出字符串，change_index"表示
new_str中哪一段索引是被改变的索引
2.第二条规则：b + cde + b + dcdc #ab b
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,3"]},
2:{"source_str":"bcdeabdcdc","new_str":"bcdebdcdc","change_index":["1,3","4"]},
}
3.第三条规则：b + cde + b + d + a + d + a #c a
此时该字典str_status为：
{1:{"source_str":"babcabdcdc","new_str":"bcdeabdcdc","change_index":["1,2,3"]},
2:{"source_str":"bcdeabdcdc","new_str":"bcdebdcdc","change_index":["1,2,3","4"]},
3:{"source_str":"bcdebdcdc","new_str":"bcdebdada","change_index":["1,2,3","4","6,8"]},
}
三、字符串按规则处理函数
传入rule_dict和原生字符串。按照规则进行处理：对于输入字符串中的每个子字符串s1，
如果该子字符串没有被之前的任何规则更改过（通过str_status判断有没有更改过），则将其替换为s2，
之后更新str_status"""
import redef read_rules_file(file_path):rule_dict = {}if "\n" in file_path:for n, line in enumerate(file_path.split("\n")):s1, s2 = line.strip().split()rule_dict[n] = [s1, s2]else:with open(file_path, 'r', encoding='utf-8') as file:for n, line in enumerate(file, start=1):s1, s2 = line.strip().split()rule_dict[n] = [s1, s2]return rule_dictdef find_substring(main_string, sub_string):indexes = [m.start() for m in re.finditer('(?={})'.format(re.escape(sub_string)), main_string)]target_index = []for index in indexes:if main_string.find(sub_string) == -1:return Falseelse:target = list(range(index, index + len(sub_string)))str_target = ",".join(map(str, target))target_index.append(str_target)return target_indexdef replace_by_indices(input_str, indices_list, replacement):new_str = list(input_str)for i, indices in enumerate(indices_list):#获取起始位置和结束位置start, end = map(int, [indices.split(',')[0], indices.split(',')[-1]])#考虑切片长度与要替换的字符串长度不等的情况len_qie = len(replacement) - (end + 1 - start)start = start + len_qie * iend = end + len_qie * inew_str[start:end + 1] = replacementreturn ''.join(new_str)def parse_number_string(s: str):"""将连续数字字符串转换为整数列表"""return [int(n) for n in s.split(',')]def check_relationship(s1: str, s2: str):"""判断两个连续数字字符串是否存在交叉或包含关系。:param s1: 第一个连续数字字符串:param s2: 第二个连续数字字符串:return: 返回关系类型，'none', 'cross', 或 'contain'"""# 将字符串转换为整数列表list1 = parse_number_string(s1)list2 = parse_number_string(s2)# 获取每个列表的边界值min1, max1 = min(list1), max(list1)min2, max2 = min(list2), max(list2)# 检查包含关系if min1 >= min2 and max1 <= max2:return Trueelif min2 >= min1 and max2 <= max1:return True# 检查交叉关系if max1 >= min2 and min1 <= max2:return Trueelif max2 >= min1 and min2 <= max1:return True# 如果既不交叉也不包含，返回 'none'return Falsedef apply_replacement_rules(rules_file, input_string: str):rule_dict = read_rules_file(rules_file)# 规则条数len_rule_dict = len(rule_dict)str_status = {}current_str = input_stringfor rule_num, (s1, s2) in rule_dict.items():if not str_status:  # 如果为空，则为第一次规则# 记录第一条规则执行前的s1的所有位置before_pro = find_substring(input_string, s1)if before_pro:  # 只有s1存在于input_string中时才考虑替换current_str = input_string.replace(s1, s2)if len(s1) == len(s2):  # 当s1等于s2的长度时直接替换并更新状态字典str_status[rule_num] = {"source_str": input_string,"new_str": current_str,"change_index": before_pro}else:  # 如果不等len_d = len(s2) - len(s1)before_pro_new = []for index_ren, index_replace in enumerate(before_pro):list_index = index_replace.split(",")if len_d < 0:  # 如果小于for i in range(abs(len_d)):list_index.pop(-1)else:  # 如果大于N_ = 0for i in range(abs(len_d)):N_ += 1list_index.append(str(int(list_index[-1]) + N_ + abs(len_d) * index_ren))list_index[0] = str(int(list_index[0]) + abs(len_d) * index_ren)list_index = ",".join(list_index)before_pro_new.append(list_index)str_status[rule_num] = {"source_str": input_string,"new_str": current_str,"change_index": before_pro_new}else:# 上次执行规则后的字符串new_str = str_status[sorted(list(str_status.keys()))[-1]]["new_str"]# 准备改动的位置before_pro = find_substring(new_str, s1)# 准备改动的位置，缓存before_pro_temp = find_substring(new_str, s1)# 已经改动的位置change_index = str_status[sorted(list(str_status.keys()))[-1]]["change_index"]# 只有s1存在于input_string中时才考虑替换if before_pro:# 每一个准备改动的位置for pre_chage in before_pro_temp:# 每一个已经改动的位置for change_part in change_index:# 如果准备改动的位置与已经改动的位置存在交叉、包含关系if check_relationship(pre_chage, change_part):# 将不可改动的位置从准备改动的位置移除before_pro.pop(before_pro.index(pre_chage))# 将可以改动的位置按索引进行替换current_str = replace_by_indices(new_str, before_pro, s2)# 状态更新before_pro_new = change_index + before_prostr_status[rule_num] = {"source_str": new_str,"new_str": current_str,"change_index": before_pro_new}return current_str, str_status# Example usage
'''常规情况'''
# rules_file = "rule.txt"
# rules_file = "abc cde\nab b\nc a"#bcdebdada
# rules_file = "c ab\nabc cde\nab b"  # bbabbdabdab
# input_string = "babcabdcdc"
# output_string, status = apply_replacement_rules(rules_file, input_string)
# print("Output String:", output_string)
# print("Status:", status)'''特殊情况'''
# rules_file = "abcd ab\ncde bcd\nade bc"#babcabdcdc
# input_string = "babcabdcdc"
# output_string, status = apply_replacement_rules(rules_file, input_string)
# print("Output String:", output_string)
# print("Status:", status)'''自测试'''
# rules_file = "ab aby\ncde bcid\nade bc\nb g"  # gabycdabydbcidc
# input_string = "babcdabdcdec"
# output_string, status = apply_replacement_rules(rules_file, input_string)
# print("Output String:", output_string)
# print("Status:", status)'''问题数据'''
# rules_file = "bcd ac\ncd ba\nab dd\nc a"  # ddaddaaacba
# input_string = "abcabcabcdcd"
# output_string, status = apply_replacement_rules(rules_file, input_string)
# print("Output String:", output_string)
# print("Status:", status)