# 11585 속타는 저녁 메뉴

```cpp
#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;
}
```

* 다소 참고 : <https://blog.naver.com/ndb796/221240660061>
* MakeLPS()는 내가 작성, FindByKMP()는 블로그 참고한 축약 버전


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined-1/11585.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.