1543 문서 검색

string class를 사용해서 쉽게 해결할 수 있다. 시작점이 어디냐에 따라서 답이 달라질 수 있으므로 모든 가능성 있는 시작점을 찾고 find를 통해 최댓값을 찾을 수 있다

 

문제: https://www.acmicpc.net/problem/1543

깃허브주소: https://github.com/surinoel/boj/blob/master/1543.cpp

 

	#include <cstring>
	#include <sstream>
	#include <iostream>
	using namespace std;
	#define max(n, m) n > m ? n : m
	char a[2501], b[51];
	char* ptrarr[2501];
	int main(void) {
	scanf("%[^\n]s", a);
	scanf(" %[^\n]s", b);
	char* ptr = a;
	int lena = strlen(a);
	int lenb = strlen(b);
	int idx = 0;
	for (int i = 0; i < lena; i++) {
	if (!strncmp(&a[i], b, strlen(b))) {
	ptrarr[idx++] = &a[i];
	}
	}
	int ans = 0;
	for (int i = 0; i < idx; i++) {
	char* staddr = ptrarr[i];
	int cnt = 0;
	while ((staddr = strstr(staddr, b)) != NULL) {
	cnt += 1;
	staddr = staddr + lenb;
	}
	ans = max(ans, cnt);
	}
	printf("%d\n", ans);
	return 0;
	}

view raw 1543.c hosted with ❤ by GitHub

	#include <vector>
	#include <string>
	#include <sstream>
	#include <iostream>
	using namespace std;
	#define max(n, m) n > m ? n : m
	vector<size_t> stidx;
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	string a, b;
	getline(cin, a);
	getline(cin, b);
	int lenA = a.length();
	int lenB = b.length();
	for (int i = 0; i < lenA; i++) {
	if (!a.compare(i, lenB, b)) {
	stidx.push_back(i);
	}
	}
	int ans = 0;
	for (int i = 0; i < stidx.size(); i++) {
	size_t idx = stidx[i];
	int cnt = 0;
	while ((idx = a.find(b, idx)) != string::npos) {
	cnt += 1;
	idx += b.length();
	}
	ans = max(ans, cnt);
	}
	cout << ans << '\n';
	return 0;
	}

view raw 1543.cpp hosted with ❤ by GitHub