문자열을 두 개 이어 붙인 다음 거기서 찾으면 한바퀴 돌리면서 찾는거랑 똑같음. 이 때 처음부터 끝까지 찾으면 하나 더 찾을수도 있으므로 한칸 건너 뛴다. ex) ABCABC에서 ABC 찾기
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 1e6+1;
int fail[MAX];
int gcd(int a, int b) {
if (!b) return a;
return gcd(b, a%b);
}
void make_fail(string& s) {
int begin = 1, match = 0;
while (begin + match < s.length()) {
if (s[begin+match] == s[match]) {
match++;
fail[begin+match-1] = match;
}
else {
if (!match) begin++;
else {
begin += match - fail[match-1];
match = fail[match-1];
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
string s, s2;
for (int i = 0; i < n; i++) {
char c;
cin >> c;
s += c;
}
for (int i = 0; i < n; i++) {
char c;
cin >> c;
s2 += c;
}
s2 += s2;
memset(fail, 0, sizeof(fail));
make_fail(s);
vector<int> v;
// s2에서 s찾기
int begin = 1, match = 0;
while (begin + match < s2.length()) {
if (match < s.length() && s2[begin+match] == s[match]) {
match++;
if (match == s.length()) v.push_back(begin);
}
else {
if (!match) begin++;
else {
begin += match - fail[match-1];
match = fail[match-1];
}
}
}
cout << v.size()/gcd(v.size(), n) << '/' << n/gcd(v.size(), n);
return 0;
}
오늘 저녁 짬이 뭐더라..