251011

lililllilillll·2025년 10월 11일

개발 일지

목록 보기

321/350

✅ 한 것들

백준
R&D : Jenkins

📝 배운 것들

🏷️ KMP 알고리즘

(실제로 문자열 검색 나오면 (gcc 아닐 땐) find() 쓰거나 rabin-karp(부분 문자열을 해시값으로 변환 후 해시값을 찾기) 쓰는게 편하다고 함)

실패 함수 (LPS)

시작부터의 접두사와 해당 인덱스부터의 접미사가 같은 가장 긴 길이
어디서 비교를 재시도 할지 기록해둔 값 (지금 비교를 실패한 문자열과 똑같은 앞의 문자열로 재도전)
실패 함수 생성에선
- 값을 len이라는 변수에 담아두며 '새로 추가된 글자'를 비교할 위치를 결정한다
- 새로운 글자가 비교 문자열과 달랐고, len!=0 이었다면, 재시도(길이를 줄이면 글자가 같아질지 확인)를 위해 len을 변경한다.
  - 이때 실패 함수의 값은 아직 결정되지 않은 채로 다음 while문 루프를 돌게 된다
- len==0이면 더 이상 비교할 문자열이 없으니 0으로 기록하고 넘어간다
KMP 비교에선
- 실패 함수 생성과 본질적으로 같다
- 글자가 다른데 len!=0이면 아직 코인이 남아있는 곳(동일한 문자열이 아직 존재하는 곳)으로 가서 새로운 글자를 다시 비교해본다.
- O(m+n)인 이유는, i를 탐색할 전체 문자열 인덱스, j를 찾아낼 부분 문자열 인덱스라 할 때,
  - i가 올라갈 때 j도 한 번밖에 못 올라가기 때문이다.
  - 내려가는 것까지 최악으로 가정하면 최대 2m 이동 가능

⚔️ 백준

11585 속타는 저녁 메뉴

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

namespace
{
	void MakeLPS(string& cmp, vector<int>& lps)
	{
		lps[0] = 0;
		int idx=1, len=0;
		while (idx<cmp.size())
		{
			if (cmp[idx] == cmp[len]) // idx : 새로운 문자, len : 기존 접두사
			{
				len++;
				lps[idx] = len;
				idx++;
			}
			else
			{
				if (len == 0) // 0으로 기록하고 다음 인덱스로 넘어간다
				{
					lps[idx] = 0;
					idx++;
				}
				else
				{
					len = lps[len - 1]; // 새 문자열 비교 재시도할 곳을 찾는다
				}
			}
		}
	}

	int FindByKMP(int n, string& rlt, string& cmp, vector<int>& lps)
	{
		int count = 0;
		int len = 0;
		for (int i = 0; i < 2*n; i++)
		{
			while (len != 0 && rlt[i] != cmp[len])
			{
				len = lps[len - 1];
			}
			if (rlt[i] == cmp[len])
			{
				len++;
                // 실수 : i-len+1<n을 안 함
                // 실수 2 : len이 더 큰데 +1을 안 함
				if (len == n && i-len+1<n)
				{
					count++;
					len = lps[len - 1];
				}
			}
		}
		return count;
	}
}


int main()
{
	// 인덱스 오류 방지 및 정확한 확률 계산을 위해
	// 룰렛 문자열을 2배로 만들고, 원본 문자열 인덱스까지만 확인한다.
	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int n;
	char temp;
	string cmp, rlt;
	vector<int> lps;
	cin >> n;
	lps = vector<int>(n);
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		cmp += temp;
	}

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		rlt += temp;
	}
	rlt += rlt;

	MakeLPS(cmp,lps);
	int cnt = FindByKMP(n,rlt,cmp,lps);
	cout << "1/" << n / cnt;
}