E. Reverses

Codeforces

IDCF906E

Time2000ms

Memory256MB

Difficulty—

dpstring suffix structuresstrings

English · Original

Chinese · Translation

Formal · Original

Hurricane came to Berland and to suburbs Stringsvill. You are going to it to check if it's all right with you favorite string. Hurrinace broke it a bit by reversing some of its non-intersecting substrings. You have a photo of this string before hurricane and you want to restore it to original state using reversing minimum possible number of its substrings and find out which substrings you should reverse. You are given a string _s_ — original state of your string and string _t_ — state of the string after hurricane. You should select _k_ non-intersecting substrings of _t_ in such a way that after reverse of these substrings string will be equal _s_ and _k_ is minimum possible. ## Input First line of input contains string _s_ and second line contains string _t_. Both strings have same length and consist of lowercase English letters. 1 ≤ |_s_| = |_t_| ≤ 5·105 ## Output In first line print _k_ — minimum number of substrings you should reverse. Next output _k_ lines. Each line should contain two integers _l__i_, _r__i_ meaning that you should reverse substring from symbol number _l__i_ to symbol _r__i_ (strings are 1-indexed). These substrings shouldn't intersect. If there are multiple answers print any. If it's impossible to restore string output _\-1_. [samples]

飓风袭击了 Berland 及其郊区 Stringsvill。你打算去那里检查你最爱的字符串是否安好。飓风通过反转其中一些不相交的子串，使字符串变得支离破碎。你有一张飓风前该字符串的照片，现在希望用最少数量的子串反转操作将其恢复为原始状态，并找出应反转哪些子串。你将获得两个字符串：#cf_span[s] —— 字符串的原始状态，以及 #cf_span[t] —— 飓风后的状态。你需要从 #cf_span[t] 中选出 #cf_span[k] 个不相交的子串，使得将这些子串反转后，字符串将变为 #cf_span[s]，且 #cf_span[k] 尽可能小。输入的第一行包含字符串 #cf_span[s]，第二行包含字符串 #cf_span[t]。两个字符串长度相同，且均由小写英文字母组成。#cf_span[1 ≤ |s| = |t| ≤ 5·105] 第一行输出 #cf_span[k] —— 你应反转的最小子串数量。接下来输出 #cf_span[k] 行，每行包含两个整数 #cf_span[li], #cf_span[ri]，表示应反转从第 #cf_span[li] 个字符到第 #cf_span[ri] 个字符的子串（字符串为 1-索引）。这些子串不应相交。若有多个答案，输出任意一个即可。若无法恢复字符串，请输出 _-1_。 ## Input 第一行输入包含字符串 #cf_span[s]，第二行包含字符串 #cf_span[t]。两个字符串长度相同，且均由小写英文字母组成。#cf_span[1 ≤ |s| = |t| ≤ 5·105] ## Output 第一行输出 #cf_span[k] —— 你应反转的最小子串数量。接下来输出 #cf_span[k] 行，每行包含两个整数 #cf_span[li], #cf_span[ri]，表示应反转从第 #cf_span[li] 个字符到第 #cf_span[ri] 个字符的子串（字符串为 1-索引）。这些子串不应相交。若有多个答案，输出任意一个即可。若无法恢复字符串，请输出 _-1_。 [samples]

**Definitions** Let $ s, t \in \Sigma^n $ be two strings of equal length $ n \geq 1 $, where $ \Sigma $ is the set of lowercase English letters. **Constraints** 1. $ |s| = |t| = n $, with $ 1 \leq n \leq 5 \cdot 10^5 $. 2. The goal is to find a set of $ k $ non-overlapping substrings of $ t $, such that reversing each of them results in $ s $. 3. The number $ k $ must be minimized. **Objective** Find the minimum $ k \in \mathbb{N}_0 $ and a sequence of non-intersecting index pairs $ (l_1, r_1), (l_2, r_2), \dots, (l_k, r_k) $ with $ 1 \leq l_i \leq r_i \leq n $, such that: $$ \text{reverse}_{(l_1,r_1)} \circ \text{reverse}_{(l_2,r_2)} \circ \cdots \circ \text{reverse}_{(l_k,r_k)}(t) = s $$ If no such set exists, output $-1$.

Samples

Input #1

abcxxxdef
cbaxxxfed

Output #1

2
7 9
1 3

API Response (JSON)

{
  "problem": {
    "name": "E. Reverses",
    "description": {
      "content": "Hurricane came to Berland and to suburbs Stringsvill. You are going to it to check if it's all right with you favorite string. Hurrinace broke it a bit by reversing some of its non-intersecting substr",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF906E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Hurricane came to Berland and to suburbs Stringsvill. You are going to it to check if it's all right with you favorite string. Hurrinace broke it a bit by reversing some of its non-intersecting substr...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "飓风袭击了 Berland 及其郊区 Stringsvill。你打算去那里检查你最爱的字符串是否安好。飓风通过反转其中一些不相交的子串，使字符串变得支离破碎。你有一张飓风前该字符串的照片，现在希望用最少数量的子串反转操作将其恢复为原始状态，并找出应反转哪些子串。\n\n你将获得两个字符串：#cf_span[s] —— 字符串的原始状态，以及 #cf_span[t] —— 飓风后的状态。你需要从 #cf...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s, t \\in \\Sigma^n $ be two strings of equal length $ n \\geq 1 $, where $ \\Sigma $ is the set of lowercase English letters.  \n\n**Constraints**  \n1. $ |s| = |t| = n $, with $ 1 \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments