백준9549🐨암호화된 비밀번호 검증

암호화된 비밀번호

한국어

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	650	204	157	31.653%

문제

새로운 암호화 알고리즘이 개발되었다.
우선, 모든 비밀번호는 항상 알파벳 소문자로만 이루어진다고 가정하자.
암호화 알고리즘은 다음과 같이 진행된다.
1. 비밀번호의 서로 다른 두 글자를 교환한다. 이 과정은 0번 또는 원하는 만큼 얼마든지 할 수 있다.
2. 1번 과정의 결과물 앞부분에 0개 혹은 그 이상의 문자를 삽입한다.
3. 2번 과정의 결과물 뒷부분에 0개 혹은 그 이상의 문자를 삽입한다.
3번 과정의 결과물이 암호화된 비밀번호이다.
청호는 사용하던 비밀번호들을 위 알고리즘대로 다 암호화했다.
하지만 수작업이었던 탓에 실수가 있을 지도 모르기 때문에 프로그램을 작성하여 제대로 암호화했는지 확인해보려 한다.
암호화된 비밀번호와 원래의 비밀번호가 주어지면, 암호화된 비밀번호가 원래의 비밀번호를 위의 알고리즘대로 암호화한 결과물일 수 있는지 혹은 없는지를 알아내 보자.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 100 )
각 테스트 케이스는 두 줄로 구성된다.
첫 줄엔 암호화된 결과물이 주어진다.
두 번째 줄엔 원래의 비밀번호가 주어진다.
암호화된 비밀번호와 원래의 비밀번호는 1개 이상 10만개 이하의 문자로 이루어져 있으며, 항상 알파벳 소문자만을 포함한다.
암호화된 비밀번호의 길이는 항상 원래 비밀번호의 길이보다 크거나 같다.

출력

각 테스트 케이스마다, 원래의 비밀번호를 문제에서 설명한 알고리즘대로 암호화했을 때 주어진 결과물이 나올 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

예제 입력 1

3
abcdef
ecd
cde
ecd
abcdef
fcd

예제 출력 1

YES
YES
NO

문제 풀이

순서를 마구 섞고 앞 뒤에 붙일 수 있다면, 순서가 섞인 암호화 이전의 문자열이 숨어 있다는 말이다.
원래 문자열 길이만큼 떼어내서 알파벳별 개수를 세고 비교하면 되지만 그러면 복잡도가 너무 커진다.

해결 방법은 슬라이딩 윈도우를 쓰는 것으로 원래 문자열 길이만큼 윈도우를 만들고 나가는 문자를 빼고 들어오는 문자를 더하는 식으로 데이터를 갱신하면 한 번의 순회로 확인할 수 있다.

 

n,*r=open(0,'rb').read().split()

n=int(n)
for i in range(0,n<<1,2):
    crypto,origin=r[i],r[i+1]
    o_width=len(origin)
    c_width=len(crypto)
    count=[0]*26
    check=[0]*26
    for char1 in origin:
        count[char1-97]+=1
    for char2 in crypto[:o_width]:
        check[char2-97]+=1
    if count==check:
        print("YES")
        continue
    for j in range(1, c_width-o_width+1):
        gone=crypto[j-1]
        come=crypto[j+o_width-1]

        check[come-97]+=1
        check[gone-97]-=1

        if count==check:
            print("YES")
            break
    else:
        print("NO")
        
'''
--------------------------------------------------
입력
--------------------------------------------------
3
abcdef
ecd
cde
ecd
abcdef
fcd
--------------------------------------------------
출력
--------------------------------------------------
a d
0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
b e
0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
YES
YES
a d
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
b e
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
c f
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
NO