문자열 비교 응용 - 다시 처음부터 되돌아가면서 비교해야할때

1. 문제

 

5555번: 반지 (acmicpc.net)

5555번: 반지

 

2. 풀이

 

보통 target 문자열 찾을때는 한줄 안에서 똑같이 있는지 찾았지만

 

이 문제는 target 문자열이 뒤로 넘어가면 다시 처음부터 되돌아가야한다

 

 

ZAAAAAAAXY에서 XYZ를 찾고자 할때,

Z                  XY

 

하면 하나를 찾을 수 있다는 뜻

 

어떻게 할 수 있을까

 

찾고자 하는 문자열 XYZ의 길이가 3이고 처음부터 끝까지 순회하는데...

 

ZAAAAAAAXY

                       XYZ에 도달하면 끝인데.. 여기서 YZ는 다시 처음 2글자 ZA와 비교해야하니까..

 

ZAAAAAAAXY 뒤에 (찾고자하는 문자열 길이-1)만큼의 문자열을 새로 붙여서

 

ZAAAAAAAXYZA로 만들고, 처음부터 원래 문자열 길이까지 브루트포스로 순회해서 비교해준다

 

 

from sys import stdin

target = stdin.readline().rstrip()

n = int(stdin.readline())

t = len(target)

count = 0

for _ in range(n):
    
    string = stdin.readline().rstrip()

    s  = len(string)
    
    #처음으로 되돌리기 위해, 
    #원래 문자열에서 비교하고자하는 문자열 길이만큼 붙여준다
    string += string[:t]

    find = False
    
    #처음부터 원래 문자열의 길이만큼 순회해준다
    for i in range(s):
        
        if target == string[i:i+t]:
            
            count += 1
            break
    
    
print(count)