E.Substring Reverse Gym - 101755E

Lokinli

发布于 2023-03-09 16:06:55

5940

发布于 2023-03-09 16:06:55

文章被收录于专栏：以终为始

Substring Reverse

Problem

Two strings s and t of the same length are given. Determine whether it is possible to make t from s using exactly one reverse of some its substring.

Input

The first line contains the string s, and the second — the string t. Both strings have the same length from 1 to 200000 characters and consist of lowercase Latin letters.

Output

Output «YES», if it is possible to reverse some substring of s to make s equal to t, and «NO», otherwise.

Examples

Input

abcdefg
abedcfg

Output

YES

Input

abcdefg
abdecfg

Output

NO

题意: 给定两个字符串s、t，能不能反转（逆序）s其中一部分子串使得和t是相同的字符串。

解析：只需要找到需要比较的区间L,R，在这个区间内比较一下是否为相反的子串，就可以了。

// By Mercury_Lc
#include <bits/stdc++.h>
using namespace std;
int main()
{
    char s[200005];
    char t[200005];
    while(~scanf("%s %s",&s,&t))
    {
        int n = strlen(s);
        int l = 0, r = n;
        for(int i = 0; i < n; i ++)
        {
            if(s[i] == t[i]) l++;
            else break;
        }
        for(int i = n; i >= 0; i --)
        {
            if(s[i]== t[i]) r --;
            else break;
        }
        //cout << l << " " << r << endl;
        int f = 0;
        for(int i = l; i <= r; i ++)
        {
            if(s[i] != t[r + l - i])
            {
                f= 1;
                break;
            }
        }
        if(f==0)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-07-31，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法