백준 1097번 : 마법의 문자열 - KMP

https://www.acmicpc.net/problem/1097

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;
}