C++ / 백준 / 5582 / 공통 부분 문자열

문제

https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

문제풀이

두 포인터 알고리즘을 이용하였다.

변수로 시작 지점(s)과 끝 지점(e)을 두고, 첫 번째 문자열에 대해 s인덱스부터 e인덱스까지 문자를 더해 새로운 문자열을 만든다.

그다음 해당 문자열이 두 번째 문자열에 있는지 find함수를 이용하여 구한다.

있다면 e를 +1 하고, 문자열에 e인덱스를 더해 새로운 문자열을 만든다.

없다면 s를 +1 하고, 문자열에 맨 앞을 erase를 이용하여 지운다. 

 

1. 처음 시작)

2. 1의 문자가 있는 경우

1의 문자가 두 번째 문자열에 있는 경우 e를 늘린다.

이러면 새로운 문자열은 string[0] + string[1]이 된다.

 

3. 2에서 새로 만든 문자열이 두 번째 문자열에 없는 경우이다.

2에서 만든 문자열이 없기 때문에 s를 1 늘려준다.

 

 

 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	string s1(""), s2("");	
	string s("");
	cin >> s1 >> s2;
	int answer(0);
	int idx1(0), idx2(0);
	
	int start(0);
	int end(0);

	s = s1[0];
	while (end <= s1.size() && start<s1.size()) {		
		if (start > end) {
			end = start;			
			s = s1[start];
		}
		else if (s2.find(s) != string::npos) {
			answer = max(answer, end - start + 1);
			end++;
			s += s1[end];
		}
		else {
			start++;
			if (!s.empty())
				s.erase(0, 1);
		}
	}
	cout << answer;
}