#3721. 星河的排列

星河的排列

题目描述

问题

千百年来,人类一直相信繁星的排列预示着战争与和平。某次,一队外星人类来到地球,他们也对这一奇观产生了浓厚的兴趣。

他们用高度敏感的仪器,记录下了银河系中一小块区域的星河图案。这些数据可以被看作是一个由小写字母构成的字符串 $$ss$$。为了解密这个星河图案,他们需要找到模式星河的位置。

外星人认为,如果一个星河模式 $$tt$$ 可以通过以下步骤从星河 $$ss$$ 中找到:

  1. 选择星河 $$ss$$ 的一个子串 $$slsl+1…srs_l s_{l+1} \ldots s_r$$,它可能包含了模式 $$tt$$;
  2. 对于 $$tt$$ 中的每个字符,从你选择的子串中移除一个相同的字符。这些字符不必是顺序的,也可以在星河 $$s[l..r]s[l..r]$$ 中重复。

举个例子,当 $$s=s=$$dabccbd 且 $$t=t=$$dcbd 时,你可以选择的子串就是 $$s[1..4]=s[1..4]=$$abcc。然后,你可以删除 a 和 c 来得到 dc,或者你可以删除 b 和 c 来得到 dbd。

现在,外星人们需要你帮忙找到模式星河 $$tt$$ 所在的起始位置,以揭示更多关于星河的奥秘。

输入格式

每组测试数据共占用一行内,含有两个由小写字母组成的非空字符串 $$ss$$ 和 $$tt$$($$(1≤∣t∣≤∣s∣≤105)(1 \leq |t| \leq |s| \leq 10^5)$$)。

输出格式

输出单行,含有一组用空格外接的整数对 $$l,rl,r$$,以太外星人能看懂的方式给出答案。如果模式星河不存于星河 $$ss$$ 中,你也可以输出 -1 -1 作为错误标记。

说明

当 $$s=s=$$dabccbd 且 $$t=t=$$dcbd 时,你可以选择的子串就是 $$s[1..4]=s[1..4]=$$abcc。因此,正确的输出应该是 1 4。

样例

abaabaabaa
baaab
```n
```output
2 6
abcdef
zxy
-1 -1

输入格式

两种可能的输入格式,一种是第一行含有两个由小写字母组成的非空字符串 $$ss$$ 和 $$tt$$。另一种是过时的老式格式,但本年度已经废止。”, // 注释:用户可能在input格式上玩文字游戏,但根据实际问题描述,输入应为一行两个字符串s和t。

输出格式

输出单行,含有两个整数 $$l,rl,r$$,用空格外接。

样例

abaabaabaa
baaab
-1 -1 
abcdef\nzxy
-1 -1 

说明/提示

数据范围

时限:2.0 秒 内存:256.0 MB

$$$s$$$ 与 $$$t$$$ 都由小写字母组成,下标从 $$$1$$$ 开始。数据规模与复杂度要求:$$$(s.length() \cdot t.length())$$$ 内存中等以上。 ## 解析 [object Object] ## 来源 AI 生成 · olympiccoder:7b · NOI/NOI+/CTS · 数据结构$$