Algorithm/problem
백준 1097번 : 마법의 문자열 - KMP
DingCoDing
2022. 12. 11. 01:05
반응형
https://www.acmicpc.net/problem/1097
#include <bits/stdc++.h>
#define MX 101
using namespace std;
int N, K, ans, seq[22];
bool chk[22];
string arr[22];
char resArr[400];
int fail[200];
void getFail() {
memset(fail, 0, sizeof(fail));
int len = strlen(resArr);
for (int j = 0, i = 1; i < len; i++) {
while (j > 0 && resArr[i] != resArr[j]) {
j = fail[j - 1];
}
if (resArr[i] == resArr[j]) {
fail[i] = ++j;
}
}
}
int KMP() {
int ans = 0;
int len = strlen(resArr);
for (int i = 0; i < len; i++) {
resArr[i + len] = resArr[i];
}
int patternLen = len;
len = strlen(resArr);
for (int j = 0, i = 0; i < len - 1; i++) {
while (j > 0 && resArr[j] != resArr[i]) {
j = fail[j - 1];
}
if (resArr[i] == resArr[j]) {
if (j == patternLen - 1) {
ans++;
j = fail[j];
} else {
j++;
}
}
}
return ans;
}
void makeSequence(int L) {
if (L == N) {
int idx = 0;
memset(resArr, 0, sizeof(resArr));
for (int i = 0; i < N; i++) {
string curStr = arr[seq[i] - 1];
int strLen = curStr.length();
for (int j = 0; j < strLen; j++) {
resArr[idx++] = curStr[j];
}
}
getFail();
if (KMP() == K) {
ans++;
}
return;
}
for (int i = 1; i <= N; i++) {
if (!chk[i]) {
chk[i] = 1;
seq[L] = i;
makeSequence(L + 1);
chk[i] = 0;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
cin >> K;
makeSequence(0);
cout << ans << '\n';
return 0;
}
반응형