1 条题解

  • 1
    @ 2024-4-6 18:33:41

    首先注意特殊情况,PP 的长度如果小于 SS, 一定是无解的。

    子任务1

    可采用遍历字符串 SS , 在 PP 中查找是否按顺序均逐一出现过。或者其他解题思路

    子任务2

    注意到该子任务的特殊性质:SS 由相同字母构成。记这个相同字母为 CC,于是我们只要在字符串 PP 中统计字母 CC 出现的次数,判断次数是否大于或等于 SS 的长度即可。

    如果字符串 PPCC 出现的次数大于或等于 SS 的长度,则(出现次数减去 SS 长度)即为答案,否则就属于 NO 的情况。

    子任务3

    设置一个记录两个字符串相同字符个数的变量 same=0same=0

    设置一个记录两个字符串长度之差的变量 delta=PSdelta=\lvert P \rvert - \lvert S \rvert

    两个记录下标用的变量 i=0,j=0i=0, j=0,分别对应 SSPP 当前处理的字符下标。

    循环逐一对比 S[i]S[i]P[j]P[j] ,如果相同,则 i++,j++,same++i++,j++,same++,继续比对下一位字符;如果不同,则 j++,deltaj++, delta--,如 delta<0delta < 0,可以提前结束断定无解,否则继续在 PP 中寻找 S[i]S[i]

    jjii 先到达字符串末尾,则说明无解。否则,Psame\lvert P \rvert - same 即为答案。

    • 1

    信息

    ID
    56
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    20
    已通过
    6
    上传者