[SWEA] C++ 2007. 패턴 마디의 길이(D2)

문제 바로가기

접근방법

1. 패턴이 되는 문자을 찾아야한다.

2. 첫 번째 문자와 같은 문자가 있는 곳을 찾아야한다.

   • 첫 번째 인덱스부터 같은 문자가 있는 곳의 인덱스까지 임시로 문자열을 만든다.
   • 같은 문자가 있는 곳의 인덱스부터 temp의 길이까지 temp와 같으면 그 문자열은 temp가 반복되는 것이다.

   1) 쉬운경우
   ex) KOREAKOREA
temp = KOREA가 된다.
   이 경우에는 KOREA의 개수를 세면 된다.

   2) 어려운 경우
   ex) SAMSUNG이 오면 temp = SAMS가 된다.
   그러면 temp를 초기화 하고 다음 인덱스부터 다시 찾는다.
   

슈도코드

if temp == str[i]
  ans = str.substr(0, i-1까지)

if str.substr(i, ans길이) == ans
  answer = ans
else
  다시 비교

풀이

#include <cstdio>
#include <iostream>
#include <queue>
#include <string>
using namespace std;

int test_case, T;
char ch;
string str, temp, answer;

void GetPattern() {
	ch = str[0];
	for (int i = 1; i < str.size(); i++) {
		if (ch == str[i]) {
			temp = str.substr(0, i);

			if (str.substr(i, temp.size()) == temp) {
				answer = temp;
				break;
			}
			else {
				temp = "";
			}
		}
	}
}

int main() {
	cin >> T;

	for (test_case = 1; test_case <= T; test_case++) {
		cin >> str;
		GetPattern();
		cout << "#" << test_case << " " << answer.size() << "\n";
	}
}