1553-B, *1300

Problem - 1553B - Codeforces

문제

• 문자열 $s(1 \leq \left | s \right | \leq 500)$와 $t(1 \leq \left | t \right | \leq 2 \cdot \left | s \right |-1)$가 주어진다
• 스케너가 임의의 $s$ 문자 위에서 오른쪽으로 갔다가 왼쪽으로 차례로 읽을 때 $t$로 읽을 수 있는가?

 

$O(t^{2}s)$

먼저 스캔했을 때 $t$가 나올 수 있는 문자열을 구하자 --- !

스케너가 오른쪽으로 갔다가 왼쪽으로 가기 시작하는 문자를 $key$라고 하자
$t$의 각 자리별로 $key$라고 생각하고 ! 을 구한다 $O(t^2log\ t)$
스케너는 항상 오른쪽을 먼저 가기 때문에 ! 의 제일 오른쪽에는 $key$가 위치한다 

이제 ! 가 $s$에 포함되는지 찾는다 $O(t^2s)$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
string s;
string t;
 
string flip(int end)
{
    int l, r;
    l = r = end;
    while(l-1 >= 0 && r+1 < t.size() && t[l-1]== t[r+1]){
        l--;
        r++;
    }
 
    string res;
    if(l == 0){
        res = t.substr(end, t.size()+end-l);
        reverse(res.begin(), res.end());
        return res;
    }
    else if(r == t.size()-1){
        return t.substr(0, end+1);
    }
    else return t;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int q;
    cin >> q;
    while(q--){
        cin >> s >> t;
        set<string> able;
        for(int right = 0; right < t.size(); right++){
            able.insert(flip(right));
        }
 
        bool flag = false;
        for(auto e: able) {
            if(s.find(e) != string::npos) {
                flag = true;
                break;
            }
        }
 
        cout << (flag? "YES": "NO") << endl;
 
    }
 
    return 0;
}cs

$O(s^{3})$

이번 풀이는 $s$에서 스케너가 길이 $\left | t \right |$만큼 스캔할 때 읽는 모든 경우를 따져본다

 

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
string s, t;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int q;
    cin >> q;
    while(q--){
        bool able = false;
        cin >> s >> t;
        for(int i = 0; i < s.size(); i++){
            for(int j = 0; j < s.size()-i; j++){
                int k = t.size() - j -1;
                int l1 = i;
                int r = i+j;
                int l2 = r-k;
                if(k < 0 || l2 < 0) continue;
 
                string part1 = s.substr(l1, j+1);
                string part2 = s.substr(l2, k);
                reverse(part2.begin(), part2.end());
 
                if(part1 + part2 == t) able = true;
            }
        }
 
        cout << (able ? "YES": "NO") << endl;
 
    }
 
 
    return 0;
}cs

두 풀이의 실제 수행시간 비교

왼쪽부터 각각 $O(t^{2}s),\ O(s^{3})$이다